First of all you will need to ensure that your database is stopped:
root@steve:~# /etc/init.d/mysql stop
Now you should start up the database in the background, via the mysqld_safe command:
root@steve:~# /usr/bin/mysqld_safe --skip-grant-tables &
[1] 6702
Starting mysqld daemon with databases from /var/lib/mysql
mysqld_safe[6763]: started
Here you can see the new job (number "1") has started and the server is running with the process ID (PID) of 6702.
Now that the server is running with the --skip-grant-tables flag you can connect to it without a password and complete the job:
root@steve:~$ mysql --user=root mysql
Enter password:
mysql> update user set Password=PASSWORD('new-password-here') WHERE User='root';
Query OK, 2 rows affected (0.04 sec)
Rows matched: 2 Changed: 2 Warnings: 0
mysql> flush privileges;
Query OK, 0 rows affected (0.02 sec)
mysql> exit
Bye
Now that you've done that you just need to stop the server, so that you can go back to running a secure MySQL server with password restrictions in place. First of all bring the server you started into the foreground by typing "fg", then kill it by pressing "Ctrl+c" afterwards.
This will now allow you to start the server:
root@steve:~# /etc/init.d/mysql start
Starting MySQL database server: mysqld.
Checking for corrupt, not cleanly closed and upgrade needing tables..
Now everything should be done and you should have regained access to your MySQL database(s); you should verify this by connecting with your new password:
root@steve:~# mysql --user=root --pass=new-password-here
Welcome to the MySQL monitor. Commands end with ; or g.
Your MySQL connection id is 5 to server version: 5.0.24a-Debian_4-log
Type 'help;' or 'h' for help. Type 'c' to clear the buffer.
mysql> exit
Bye