Além dos comandos acima (não há garantia de que todos eles são de fato necessários), faça
sudo rm -r /var/lib/mysql
Usuários e senhas (incluindo a senha raiz) são armazenados no próprio banco de dados, e o diretório de dados padrão é /var/lib/mysql .