0) Eu estou supondo que você já tentou sudo apt-get install -f
1) Faça o backup de seus arquivos MySQL existentes. Você pode descobrir onde seu diretório de dados está em /etc/mysql/my.cnf
Você pode usar o mysqldump para fazer backup.
2) Execute estes comandos
sudo apt-get remove --purge 'mysql*'
sudo rm -rf /etc/mysql /var/lib/mysql
sudo apt-get autoremove
sudo apt-get autoclean
sudo apt-get install mysql-server