Primero, inicie su mysql sin leer la tabla de usuario:mysqld --skip-grant-tables
Luego ejecute mysql_upgrade
que ahora debería funcionar sin problemas.
Siguiente parada mysqld:killall mysqld
.
Ahora debería poder iniciar su servicio mysql normalmente de nuevo.