Descobri que o mysql.sock é excluído quando o serviço mysql é interrompido e mysqld_safe não pode criá-lo (não consegui encontrar o motivo), então minha solução foi fazer backup da pasta sock e restaurar antes de iniciar mysqld_safe
Iniciar servidor
$ sudo service mysql start
Ir para a pasta de meias
$ cd /var/run
Faça backup da meia
$ sudo cp -rp ./mysqld ./mysqld.bak
Parar servidor
$ sudo service mysql stop
Restaurar a meia
$ sudo mv ./mysqld.bak ./mysqld
Iniciar mysqld_safe
$ sudo mysqld_safe --skip-grant-tables --skip-networking &
Iniciar shell mysql
mysql -u root
Mudar senha
FLUSH PRIVILEGES;
SET PASSWORD FOR [email protected]'localhost' = PASSWORD('my_new_password');