Well, let's first clarify that I have read all questions from Ask Ubuntu about this issue and I have followed all steps from the official docs:
I'm using Ubuntu 16.04.1 LTS
So before someone suggests anything that I've probably already tried, I'm going to show what I did:
root@localhost:/# sudo /etc/init.d/mysql stop [ ok ] Stopping mysql (via systemctl): mysql.service.
MySQL stopped correctly.
root@localhost:/# sudo /usr/sbin/mysqld --skip-grant-tables --skip-networking &  3316 root@localhost:/#
Here I don't know if this was working or not, so I follow the steps anyway.
root@localhost:/# mysql -u root ERROR 2002 (HY000): Can't connect to local MySQL server through socket '/var/run/mysqld/mysqld.sock' (2) root@localhost:/#
It seems it does not work, as service is not started. As I can't continue with the next steps I try the other method (purge).
sudo apt-get --purge remove sudo apt-get install
I try the next step:
root@localhost:/# mysqladmin -u root password MyNewPassword mysqladmin: connect to server at 'localhost' failed error: 'Access denied for user 'root'@'localhost' (using password: NO)' root@localhost:/#
As this also don't work I've tried other methods mentioned on the mysql web:
So I kill mysql process as pointed there and then I use
root@localhost:/# mysqld_safe --init-file=/home/me/mysql-init &  5267 root@localhost:/# 2017-02-01T12:47:49.250083Z mysqld_safe Logging to syslog. 2017-02-01T12:47:49.252427Z mysqld_safe Logging to '/var/log/mysql/error.log'. 2017-02-01T12:47:49.254765Z mysqld_safe Logging to '/var/log/mysql/error.log'. 2017-02-01T12:47:49.257045Z mysqld_safe Directory '/var/run/mysqld' for UNIX socket file don't exists. + Salida 1 mysqld_safe --init-file=/home/me/mysql-init root@localhost:/#
Now is when I was getting out of options, so I also try another method mentioned here on Ask Ubuntu:
root@localhost:/# sudo dpkg-reconfigure mysql-server-5.7 Checking if update is needed. This installation of MySQL is already upgraded to 5.7.17, use --force if you still need to run mysql_upgrade root@localhost:/#
And now I'm really out of options, so any suggestions are welcome.