Por padrão Debian / Ubuntu / Mint tem um usuário com acesso administrativo, usado para desligar o MySQL, chamado debian-sys-maint
.
Vá para o arquivo /etc/mysql/debian.cnf
que tem como formato:
[client]
host = localhost
user = debian-sys-maint
password = XXXXXXXX
socket = /var/run/mysqld/mysqld.sock
Leve daí a senha, que é gerada aleatoriamente ao instalar o MySQL (por exemplo, ele difere entre os servidores);
E entre no seu MySQL com:
mysql -udebian-sys-maint -pXXXXXXXX
Depois disso, você pode alterar sua senha de root.
SET PASSWORD FOR 'root'@'localhost' = PASSWORD('new_password');
Esteja ciente de que isso mudou um pouco no MySQL 5.7. Dê uma olhada em Como alterar a raiz do MySQL 'password usando o MySQL v5.7?