É difícil ver em qual configuração seu sistema realmente está, com todos os comandos que você tentou. Você leu o /usr/share/doc/mysql-server-5.5/README.Debian
como sugerido na primeira parte?
De qualquer forma, eu tentaria:
sudo dpkg-reconfigure mysql
Isto lhe dará a chance de inserir uma senha root para o MySQL (não confundir com linux root
user.
Se for bem sucedido, para iniciar o MySQL:
sudo service mysql start