/usr/bin/ld: cannot find -lz

I had the exact same error, and like you, installing zlib1g-dev did not fix it. Installing lib32z1-dev got me past it. I have a 64 bit system and it seems like it wanted the 32 bit library.

For x64 install zlib1g-dev.

sudo apt-get install zlib1g-dev

I don't need all the x86 libs ;)

sudo apt-get install libz-dev in ubuntu.