Eu tive o mesmo problema na VM com o Ubuntu 14.04. A única coisa que funcionou para mim é semelhante ao que Richard Uijen sugeriu:
sudo apt-get --purge remove mysql*
sudo apt-get autoremove mysql*
sudo rm -rf /etc/mysql/
sudo rm -rf /var/lib/mysql/
sudo apt-get clean
sudo apt-get update
sudo apt-get install --reinstall mysql-client-5.6
Basicamente você precisa remover todos os pacotes mysql (mysql *), limpar e instalar novamente
Depois disso eu pude instalar o php7 mysql client sem problemas
sudo apt-get install libapache2-mod-php7.0 php7.0-mysql