There is a nice trick allowing to change a forgotten root password for MySQL on Debian Linux without database stopping. Just look into this file.

# cat /etc/mysql/debian.cnf 
# Automatically generated for Debian scripts. DO NOT TOUCH!
[client]
host     = localhost
user     = debian-sys-maint
password = u372tK6cEsTLbz0n
socket   = /var/run/mysqld/mysqld.sock
[mysql_upgrade]
host     = localhost
user     = debian-sys-maint
password = u372tK6cEsTLbz0n
socket   = /var/run/mysqld/mysqld.sock
basedir  = /usr

Simply login using this credentials and execute the query as follows.

mysql> SET PASSWORD FOR root@localhost = password('new-password');

Debian-sys-maint account was used as a backdoor ;).