After you install the missing zlib dev package you can also use pythonbrew to uninstall and then reinstall the version of python you wanted and it seems like it picks up the new package to compile to correct abilities. This way you can keep using pythonbrew and don't have to do the compilation yourself (though it isn't that difficult)