Start the MySQL server instance or daemon with the --skip-grant-tables option (security setting).

$ mysqld --skip-grant-tables

Execute these statements.

$ mysql -u root mysql
$mysql> UPDATE user SET Password=PASSWORD('my_password') where USER='root';
$mysql> FLUSH PRIVILEGES;

If the GRANT ALL doesn't work, try:

Stop mysqld and restart it with the --skip-grant-tables option.
Connect to the mysqld server with just: mysql (i.e. no -p option, and username may not be required).

Issue the following commands in the mysql client:

UPDATE mysql.user SET Grant_priv='Y', Super_priv='Y' WHERE User='root';

FLUSH PRIVILEGES;

After that, you should be able to run GRANT ALL ON *.* TO 'root'@'localhost'; and have it work.