On a Debian system,
sudo dpkg-reconfigure localeswould prompt you with a nice menu allowing you to select new locales... Unfortunately, this is not the case with Ubuntu. You just get to generate or update the already selected locales. This is actually an Ubuntu bug, confirmed (with status: wishlist).
However, no need to despair - there's actually a fix for this (suitable for scripting automations too).
In /usr/share/i18n/SUPPORTED you get a list of available locales (the same list that on a Debian system comes at sudo dpkg-reconfigure locales as a menu).
You just need to add the lines from /usr/share/i18n/SUPPORTED you're interested in in the file /var/lib/locales/supported.d/local and then run sudo dpkg-reconfigure locales to add the new locales.
As an example, if I'm interested to add all the available Romanian locales on my system I'd need to run as root:
grep ^ro /usr/share/i18n/SUPPORTED >> /var/lib/locales/supported.d/local...So, there is a way!