Então eu consegui instalar com sucesso a última versão do MySQL usando o seguinte.
Mais uma vez, vamos limpar tudo
sudo apt-get remove --purge *mysql*
sudo rm -rf /etc/mysql /var/lib/mysql
sudo apt-get remove --purge *mariadb*
sudo apt-get autoremove
sudo apt-get autoclean
e novamente, verificamos que tanto o MySQL quanto o MariaDB foram removidos
dpkg -l | grep mariadb
dpkg -l | grep mysql
Corrija qualquer problema no bloqueio do dpkg seguindo as etapas descritas nesta resposta:
Agora obtenha e reinstale o MySQL
cd /tmp/ && wget https://dev.mysql.com/get/mysql-apt-config_0.8.10-1_all.deb
sudo dpkg -i mysql-apt-config_0.8.3-1_all.deb
sudo apt-get update
sudo apt-get install mysql-server mysql-client