Se não tiver que ser "zip", mas em vez disso, algo que suporte arquivos .zip, você sempre pode fornecer p7zip um ir.
Também vale a pena tentar seria o pacotes para zip do Ubuntu 8.04. Descompacte pode ser encontrado aqui também.
Eles são versões idênticas às mencionadas na questão para o Debian, e eu geralmente descobri que, para coisas como essa, o Debian e o Ubuntu são bastante intercambiáveis.
Se você achar que o arquivo .deb não funciona, você pode sempre procurar dentro dele pelos binários zip e unzip, com
ar vx path/to/file.deb
então tar xzvf data.tar.gz
e depois veja se você pode encontrar os arquivos dentro do pacote debian.