Note: the indented bits are intended to be copy/pasted. If you don't know your way around a unix system, and on top of that whatever weird design desisions ubuntu has implemented, it's very easy to mess them up.
Kill mysql and start it up in a completely unprivileged mode:
sudo /etc/init.d/mysql stop
sudo mysqld_safe --skip-grant-tables &
Now, mysqld_safe
will block input, so you'll need to open a new terminal tab. Then, connect to mysql's meta database that includes auth information:
mysql -uroot mysql