1. First stop the MySQL service

   /etc/init.d/mysqld stop

2. Prepare w file, which contains new credentails:

   For example /tmp/mysql-init

   UPDATE mysql.user SET Password=PASSWORD('YOUR_NEW_PASSWORD') WHERE User='root';
   FLUSH PRIVILEGES;

3. Run the mysql_safe with the newly created file:

   mysqld_safe --init-file=/tmp/mysql-init &

4. start the MySQL service

   /etc/ini.d/mysqld restart

Complete guide can be found here: https://dev.mysql.com/doc/refman/5.0/en/resetting-permissions.html