You have have root access to your system without even loging in by booting into single user mode. You can do so by a simple command at boot loader. Here is how to do that in the most popular boot loaders LILO and GRUB. You can also use a linux boot disk similarly if you are not using a boot loader.

LILO
Just enter 'linux -s' or 'linux single' (without quotes) at the LILO boot prompt.

GRUB
Hit 'e' at the Grub screen and then add 'single' to the kernel line and boot.

Now you have booted into the single user mode and have root access you can simple type 'passwd' at the shell prompt to change the root password. It would not even ask you for the old password before setting the new one.
Now press Ctrl+D to restart and boot as normal.