The Debian-way with
dpkg-reconfigure locales does not work, at least the usual menu to choose the locales does not appear.
So you have to manually edit the file
/var/lib/locales/supported.d/local and add the needed locales:
en_GB.UTF-8 UTF-8 en_US.UTF-8 UTF-8 de_DE.UTF-8 UTF-8 en_GB ISO-8859-1 en_GB ISO-8859-15 en_US ISO-8859-1 en_US ISO-8859-15 de_DE ISO-8859-1 de_DE ISO-8859-15
After that you can run
dpkg-reconfigure locales and your new locales will be created.