O procedimento é bem simples:
1) Parar o processo do MySQL
/etc/init.d/mysql stop
2) Subir o MySQL sem as tabelas de validação de usuário
mysqld_safe --skip-grant-tables &
3) Conectar ao mySQL sem senha com privilégios de root
mysql -u root
4) Criar uma nova senha de root
mysql> use mysql;
mysql> update user set password=PASSWORD("NOVA-SENHA-DE-ROOT") where User='root';
mysql> flush privileges;
mysql>quit
5) Subir novamente o serviço do MySQL
/etc/init.d/mysql stop
