There is also a Compress::Zlib::Perl which should be able to just copy onto your webhost without doing any compilation. Note that it only partially implements the Compress::Zlib API so depends on what you are doing.

So in short, this module is impossible for me to install on my webhost?

That depends on the details of what your web host makes available to you and allows you to do on your own. Do they allow you to compile c programs? Do they have a policy against you compiling your own code? If they don't provide a c compiler, but don't mind what you install in your own space, you might find a precompiled copy of gcc somewhere and copy it to your account (assuming you have enough space to do so). You might even be lucky enough to find a precompiled version of Compress::ZLib somewhere and save yourself the hassle.
--DrWhy

"If God had meant for us to think for ourselves he would have given us brains. Oh, wait..."

A properly installed module may span multiple directories, possibly including compiled libraries, 'auto' directories housing autoload methods in some format, and so on. For this reason it's often not effective to just copy a module to your hard drive and plop it into a directory under ~/site/lib.

There is a good discussion on installing modules, including links to more thorough descriptions, in Catagorized Questions and Answers, here: Installing modules. Read and follow the advice you find there, and your problem will probably resolve itself.