I had the same problem yesterday on Centos, (and tried the same things you did and got the same results).

Then I tried:

$ ls -l /usr/lib/libz*
lrwxrwxrwx  1 root root    15 Feb 14 20:24 /usr/lib/libz.so.1 -> libz.
+so.1.2.1.2
-rwxr-xr-x  1 root root 63624 Jul 21  2005 /usr/lib/libz.so.1.2.1.2
[download]

i.e. there was no libz.so, so I made a symlink to it:

$ ln -s /usr/lib/libz.so.1.2.1.2 /usr/lib/libz.so
$ ls -l /usr/lib/libz*
lrwxrwxrwx  1 root root    24 Jul 22 12:10 /usr/lib/libz.so -> /usr/li
+b/libz.so.1.2.1.2
lrwxrwxrwx  1 root root    15 Feb 14 20:24 /usr/lib/libz.so.1 -> libz.
+so.1.2.1.2
-rwxr-xr-x  1 root root 63624 Jul 21  2005 /usr/lib/libz.so.1.2.1.2
[download]

and this allowed the install to succeed.