O problema era que o valor do plugin mysql.user estava vazio para todos os usuários incluindo debian-sys-maint, então eu não poderia nem mesmo reconfigurar o pacote. Era para ser corrigido rodando mysql_upgrade mas por alguma razão não era.
Então fiz o despejo de todos os bancos de dados, removi completamente o servidor MySQL e depois o reinstalei e importei meus bancos de dados de volta.
Descarregue todos os seus bancos de dados:
> mysqldump -u root -p --databases db1 db2 > alldb.sql
Foi muito bobo da minha parte, mas fiz um despejo de todos os bancos de dados com - todos os bancos de dados. Ele incluía a tabela mysql.user onde todos os usuários tinham um valor "plugin" vazio, então eu corri o mesmo problema após a primeira reinicialização do serviço mysql. Então, depois disso, fiz o despejo apenas para meus bancos de dados.
O dump será colocado na pasta de onde você executou o comando
Remova o MySQL e suas configurações:
> sudo apt-get purge mysql-server mysql-client mysql-common mysql-server-core-5.7 mysql-client-core-5.7
> sudo rm -rf /etc/mysql /var/lib/mysql
> sudo apt-get autoremove
> sudo apt-get autoclean
Instale o MySQL:
> sudo apt-get install mysql-server
Importe seus bancos de dados de volta:
> mysql -u root -p < alldb.sql