I installed Kali Linux from the mini ISO, so I ended up with a fully functioning Linux system but with little to no tools (just nmap and ncat).
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.