Sem ter que reiniciar o MySQL, na instalação Debian padrão (e eu também suponho no Ubuntu), existe um usuário administrativo com toda a energia que você pode usar para recuperar sua senha root (ela é normalmente usada por scripts de configuração de pacotes). Você pode ter um shell MySQL com o comando:
mysql --defaults-file=/etc/mysql/debian.cnf
Depois, você pode usar a mesma consulta sugerida por Andy para redefinir a senha.