Comparto la solución que encontré:
1. Levantamos mysqld en modo seguro (mysqld_safe):
$ sudo service mysql stop
$ sudo mkdir -p /var/run/mysqld
$ sudo chown mysql:mysql /var/run/mysqld
$ sudo mysqld_safe --skip-grant-tables --skip-syslog --skip-networking &
3. Ahora podemos entrar en mysql sin contraseña:
$ mysql
mysql>
4. Cambiamos el plugin de autenticación y la password del usuario root:
mysql> update mysql.user set authentication_string = concat('*', upper(sha1(unhex(sha1('password'))))), plugin = 'mysql_native_password' where user = 'root';
5. Salimos de mysql y paramos el servidor mysqld en modo seguro:
mysql> exit
$ mysqladmin --user=root -p shutdown
6. Levantamos el servidor normal de mysql y probamos la nueva contraseña:
$ sudo service mysql start
$ mysql --user=root -p