Acabei de ter o mesmo problema ao tentar instalar algumas dependências para compilar o Ruby.
A maneira mais fácil de sair dessa miséria é anotar o pacote e a versão na segunda à última linha: zlib1g e 1:1.2.8.dfsg-2ubuntu4 , em seguida, emita o seguinte comando:
$ sudo apt install zlib1g=1:1.2.8.dfsg-2ubuntu4
Isso fará o downgrade de zlib1g para a versão exigida e a instalação deverá ser bem-sucedida posteriormente.