Eu tive o mesmo problema e tentei muitas opções. E eu tive muitos problemas com libdbd-mysql-perl
; o sistema disse que não iria instalar essa biblioteca.
Então eu pensei em instalá-lo com o Aptitude que instala um pacote e corrige todas as dependências.
Se você não tem aptitude, pode obtê-lo assim: sudo apt-get install aptitude
Primeiro tudo que você precisa para desinstalar o seu mysql existente.
Em seguida, você precisa instalar o pacote que deseja.
sudo aptitude install mysql-server-5.6
O aptitude oferece muitas opções, o que fazer. As primeiras opções são manter o pacote atual.
Então pressione (N) o até encontrar a opção que diz para fazer o downgrade dos próximos pacotes:
libmysqlclient20 [5.7.14-1ubuntu16.04 (<NULL>, now) -> 5.7.13-0ubuntu0.16
mysql-common [5.7.14-1ubuntu16.04 (<NULL>, now) -> 5.6.30-1+deb.sury.org
pressione (Y) es e o aptitude irá instalar o mysql-server-5.6. Aqui está a opção que você deve aceitar:
Se depois disso o sistema não puder se conectar ao servidor mysql, você precisará reiniciar o seu computador.