tested on Linux debian7 3.2.0-4-amd64 #1 SMP Debian 3.2.46-1+deb7u1 x86_64 GNU/Linux

in any case you need to stop current mysql operation:

/etc/init.d/mysql stop; # stop mysql service
# if that did not help try:
killall mysqld;

now you have two options:

easy way option1 (tested works – but not so official/universal)

apt-cache search mysql-server; # search for mysql binary
mysql-server - MySQL database server (metapackage depending on the latest version)
mysql-server-5.5 - MySQL database server binaries and system database setup
mysql-server-core-5.5 - MySQL database server binaries
auth2db - Powerful and eye-candy IDS logger, log viewer and alert generator
mariadb-server-10.0 - MariaDB database server binaries
mariadb-server-core-10.0 - MariaDB database core server files

dpkg-reconfigure mysql-server-5.5; # restart config

option2 (official and tested/universal)

/usr/sbin/mysqld --skip-grant-tables --skip-networking & # start with default previliges
mysql -u root; # login to mysql (you will not be asked for a password)

FLUSH PRIVILEGES; # update mysql priviliges

USE mysql;
UPDATE user SET Password = PASSWORD('root') WHERE Host = 'localhost' AND User = 'root';

USE mysql;
UPDATE user SET Password = PASSWORD('root') WHERE Host = '%' AND User = 'root';

FLUSH PRIVILEGES;

exit;
admin