Reboot the server and spam any key until you reach the grub menu.
At the grub menu select your image (in older versions, highlight your image and press e), navigate to the kernel /vmlinuz option and press e again.
Then append "init=/bin/bash" to the end of the kernel line.
Press ctrl-x to boot and you should reach a prompt.
At this point the filesystem should only be read-only. Remount the filesystem so that it's writable.
mount -o remount rw /
Change the root password.
passwd
Reboot the server and login.