You should run mysql_secure_installation as root that will prompt you for mysql root password and there just hit enter

There is probably a root password stetup there normally you should run mysql_secure_installation as root that will prompt you for mysql root password and there just hit enter.

In your case it looks like there is a root password setup you can change it by using

sudo mysqld_safe --user=mysql --pid-file=/var/run/mysql/mysqld.pid --socket=/var/run/mysql/mysql.sock --datadir=/var/lib/mysql --skip-grant-tables

This will let you start mysql and you can mysql -u root into mysql after that is matter of updating root password.

mysql> use mysql; 
mysql> update user set password=PASSWORD("yournewrootpasshere") where User='root';
mysql> flush privileges;
mysql> quit

--skip-grant-tables option is the key using that it will not prompt for a password.

After this if you restart mysql normally it will come up and you can even run mysql_secure_installation again with you new root pass if you want.

Since this is a fresh install you can also remove mysql package and reinstall it as well. Remember to remove database as well.