Solution 1:

First, remove MySQL:

sudo apt purge mysql-server mysql-client mysql-common
sudo apt autoremove
sudo mv -iv /var/lib/mysql /var/tmp/mysql-backup
sudo rm -rf /var/lib/mysql*

Then reinstall:

sudo apt update
sudo apt install mysql-server
mysqld --initialize
sudo /usr/bin/mysql_secure_installation

Solution 2:

In Ubuntu 16.04 the way to fix it in my case was (please backup DBs first, databases will be lost):

sudo apt remove --purge mysql-server mysql-client mysql-common
sudo apt autoremove
sudo mv -iv /var/lib/mysql /var/tmp/mysql-backup
sudo rm -rf /var/lib/mysql*
sudo apt install mysql-server

(Somehow, my previous calls to apt purge mysql-server didn't seem to succeed. I thought that apt purge foo was equivalent to apt remove --purge foo...)

Solution 3:

I was getting the exact same errors and tried most of the steps you did, with the same results. The following finally worked for me.

apt-get purge mysql-server mysql-client mysql-common mysql-client-5.5 mysql-server-5.5

After that, mysql installed normally.

Solution 4:

I am not sure what was the case for me, but the other solutions did not work, it kept giving an error. I tried this apt-get purge mysql-*, then autoremove and autoclean. After that installation was fine.

**

Be sure to backups your databases, the above command might delete them as well

**