I've encountered very interesting issue when trying to install python-setuptools. It went ahead doing stuff and then threw a bunch of errors like:

Nothing I did helped and there was no fix for it. Someone suggested installing Java7 to make this go away, but I've dropped that after wondering around through oracle site for a bit.

The solution came when I've stared to wonder what's my java version and wrote simple thing with not so simple error:

So java is trying to tell me that about 2gb of memory is not enough for it to start... And the memory bloat thing is a known thing for OpenVZ containers trying to run java stuff. Usually you need to have atleast 4gb of ram to start java although it does not use it all, but reserves.

The solution: went to control panel of vps and for time being increased memory up to 8gb everything installed.