Então, depois de muitos meses com esse problema, eu finalmente resolvi isso:
cd /var/lib/dpkg/info
sudo mv mysql-server-5.7* ~/mysql-conf-bk-files
sudo dpkg --remove --force-remove-reinstreq mysql-server-5.7
Eu usei a fonte nos comentários, mas o link não está mais disponível, então usei o archive.org para recuperar as informações.