MySQL – How to Install MySQL 5.6 on Ubuntu 16.04

I had the same issue on VM with Ubuntu 14.04. The only thing worked for me is similar to what Richard Uijen has suggested:

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

Basically you need to remove all mysql packages (mysql*), clean and install again

After that I could install php7 mysql client without any issues

sudo apt-get install libapache2-mod-php7.0 php7.0-mysql

You can recover or set root password without knowing the current one by starting mysql without loading the grant-tables.

Please note the $ in the commands. This is specifying the terminal prompt you see when typing in the command. It's showing it's a line of text, but and actual typed terminal command. The "mysql>" prefix is also a prompt. That is the prompt you get when running mysql interactivately.

This is the cli (command line) to do this:
(Be sure to stop the current server before performing the steps. Only one server can run at a time.)

$ sudo mkdir /var/run/mysqld; sudo chown mysql /var/run/mysqld
$ sudo mysqld_safe --skip-grant-tables&

Now you can log in as root without a password and perform all commands, as in this case, set the root password as root.

$ sudo mysql --user=root mysql

This is the set root password that you will perform inside mysql if you have MySQL 5.6 or below:

mysql> update user set Password=PASSWORD('new-password') where user='root';
flush privileges;

In MySQL 5.7 or above

mysql> update user set authentication_string=PASSWORD('new-password') where user='root';
flush privileges;

From there, quit (kill the running msqld) mysql and start it as normal.

Notes on starting and stopping the mysql service:

Stop mysql:

$ sudo service mysql stop

Start mysql (normal):

$ sudo service mysql start

Kill the temporary mysql safe mode session:

$ sudo mysqladmin shutdown