On éteint le service MySQL :

# service mysql stop

On démarre le service MySQL sans tenir compte des droits :

# /usr/bin/mysqld_safe --skip-grant-tables &

On se connecte :

# mysql -h localhost

Et on réinitialise le password de l'utilisateur root :

mysql> UPDATE `mysql`.`user` SET `Password` = password('NOUVEAU-PASSWORD') WHERE `User` = "root" AND Host = "localhost";
Query OK, 0 rows affected (0.00 sec)
Rows matched: 1  Changed: 0  Warnings: 0

On quitte mysql :

mysql> quit
Bye

On coupe le mysqladmin :

# mysqladmin shutdown 
160325 14:30:06 mysqld_safe mysqld from pid file /var/run/mysqld/mysqld.pid ended

On relance le service :

# service mysql start

Et on s'y connecte avec le nouveau mot de passe :

# mysql -u root -p

:-)

Bonus :
Pour voir les utilisateurs existants :

mysql> select Host,User,Password from mysql.user;