In order to install the tools that are making Kali what it is, I had to install the metapackages. For me, the easiest option was to install all of them (kali-linux-all).

It sounds simple:

# apt-get install kali-linux-all

but it was failing constantly

Failed to fetch http://http.kali.org/kali/pool/main/##whatever_package## Size mismatch

A little bit of research and trying to download the actual package from the host machine made me realize that the proxy was blocking access to the packages.

I decided to check if Tor traffic is allowed. Luckily it was. So I installed it

# apt-get install tor

started it

# tor &

and used torify to pass all the traffic through Tor

# torify apt-get install kali-linux-all

A few more minutes (6+ GB) and I had my fully featured Kali installation.