The python library installed on your system (or at least the one you
targeted with virtualenv -p ???) is missing the module to allow for
zlib encoding. I found this module in my python directory
(/usr/local/lib/python2.6/encodings/zlib_codec.py). Check that this
file exists in the library you're using to make the virtual
environment from.
If you tried to compile python from source, then you probably just
need to make sure that you have the zlib development headers and
compile it again, otherwise that module will not be installed into the
python standard library.
Never tried it, so I couldn't say. All I know is that in my situation
(running on my own Debian system w/ root access) you would get that
error if you tried compiling without the zlib development package
(this would be different than just having a zlib binary on the system
itself). I would imagine, though, that you could've created your own
personal compilation, so long as you made sure that you correctly set
up the paths correctly, but once again I've never tried it so I can't
be sure.