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.