Can't set locales Ubuntu 16.04

Can't set locales, that's pretty it. My VPS gives me a mutilated Ubuntu 16.04 distro:

$ export LC_ALL="en_US.UTF-8"

-bash: warning: setlocale: LC_ALL: cannot change locale (en_US.UTF-8)

$ locale -a

locale: Cannot set LC_CTYPE to default locale: No such file or directory
locale: Cannot set LC_MESSAGES to default locale: No such file or directory
locale: Cannot set LC_COLLATE to default locale: No such file or directory
C
C.UTF-8
POSIX

$ locale

locale: Cannot set LC_CTYPE to default locale: No such file or directory
locale: Cannot set LC_MESSAGES to default locale: No such file or directory
locale: Cannot set LC_ALL to default locale: No such file or directory
LANG=en_US.UTF-8
LANGUAGE=
LC_CTYPE="en_US.UTF-8"
LC_NUMERIC="en_US.UTF-8"
LC_TIME="en_US.UTF-8"
LC_COLLATE="en_US.UTF-8"
LC_MONETARY="en_US.UTF-8"
LC_MESSAGES="en_US.UTF-8"
LC_PAPER="en_US.UTF-8"
LC_NAME="en_US.UTF-8"
LC_ADDRESS="en_US.UTF-8"
LC_TELEPHONE="en_US.UTF-8"
LC_MEASUREMENT="en_US.UTF-8"
LC_IDENTIFICATION="en_US.UTF-8"
LC_ALL=en_US.UTF-8

$ sudo locale-gen "en_US.UTF-8"

sudo: locale-gen: command not found

$ sudo apt-get install locale-gen

Reading package lists... Done
Building dependency tree       
Reading state information... Done
E: Unable to locate package locale-gen

What are my options?

UPDATE for Gunnar:

$ sudo apt install --reinstall locales
Reading package lists... Done
Building dependency tree       
Reading state information... Done
0 upgraded, 0 newly installed, 1 reinstalled, 0 to remove and 0 not upgraded.
Need to get 0 B/3213 kB of archives.
After this operation, 0 B of additional disk space will be used.
perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
        LANGUAGE = (unset),
        LC_ALL = (unset),
        LANG = "en_US.UTF-8"
    are supported and installed on your system.
perl: warning: Falling back to the standard locale ("C").
debconf: unable to initialize frontend: Dialog
debconf: (No usable dialog-like program is installed, so the dialog based frontend cannot be used. at /usr/share/perl5/Debconf/FrontEnd/Dialog.pm line 76, <> line 1.)
debconf: falling back to frontend: Readline
Preconfiguring packages ...
(Reading database ... 27980 files and directories currently installed.)
Preparing to unpack .../locales_2.23-0ubuntu10_all.deb ...
Unpacking locales (2.23-0ubuntu10) over (2.23-0ubuntu10) ...
Processing triggers for man-db (2.7.5-1) ...
Setting up locales (2.23-0ubuntu10) ...
debconf: unable to initialize frontend: Dialog
debconf: (No usable dialog-like program is installed, so the dialog based frontend cannot be used. at /usr/share/perl5/Debconf/FrontEnd/Dialog.pm line 76.)
debconf: falling back to frontend: Readline
Generating locales (this might take a while)...
Generation complete.

$ locale
locale: Cannot set LC_CTYPE to default locale: No such file or directory
locale: Cannot set LC_MESSAGES to default locale: No such file or directory
locale: Cannot set LC_ALL to default locale: No such file or directory
LANG=en_US.UTF-8
LANGUAGE=
LC_CTYPE="en_US.UTF-8"
LC_NUMERIC="en_US.UTF-8"
LC_TIME="en_US.UTF-8"
LC_COLLATE="en_US.UTF-8"
LC_MONETARY="en_US.UTF-8"
LC_MESSAGES="en_US.UTF-8"
LC_PAPER="en_US.UTF-8"
LC_NAME="en_US.UTF-8"
LC_ADDRESS="en_US.UTF-8"
LC_TELEPHONE="en_US.UTF-8"
LC_MEASUREMENT="en_US.UTF-8"
LC_IDENTIFICATION="en_US.UTF-8"
LC_ALL=

$ sudo locale-gen "en_US.UTF-8"
Generating locales (this might take a while)...
  en_US.UTF-8... done
Generation complete.

$ export LC_ALL="en_US.UTF-8"
-bash: warning: setlocale: LC_ALL: cannot change locale (en_US.UTF-8)

Solution 1:

Those steps work well.

apt-get update
apt-get install -y locales
locale-gen "en_US.UTF-8"
update-locale LC_ALL="en_US.UTF-8"

Log out and log in.

export LC_ALL=en_US.UTF-8

Solution 2:

First, verify if your locate is installed, list the current locates:

locale -a

Then if your locate isn't installed, install it using this command:

sudo dpkg-reconfigure locales

Then set your locate:

export LC_ALL=en_US.UTF-8