Deus existe! : D
O problema foi resolvido ao entrar:
sudo apt-get -f install
sem outros parâmetros
e depois exibindo todos os pacotes via:
sudo dpkg -l | grep mariadb
sudo dpkg -l | grep mysql
e removendo pacotes problemáticos na ordem correta:
sudo apt-get --purge autoremove package_name
Após a remoção completa de todos os pacotes problemáticos, eu pude reinstalar o MySQL sem nenhum problema ...
Obrigado @waltinator pela sua ajuda.