Reset Root Password from console or root single user mode

So we have disabled root ssh to our linux boxes now.  But to reset the root password we need to login as a approved ssh user (/etc/ssh/sshd_conf AllowUsers bacuff for example) then su root

Enter old root password

then passwd change to new root password

or - if you have no valid ssh users (bad but we foudn ourselves in this case today on our important shared web and mail server):

I'd first see if they can get in with the root pw first on the console, if that does not work, you would reboot, and when you get to the grub boot loader, you press e for edit, the second entry, you modify, and you put 'single' at the end of that line, then boot that up, it will drop you into root single user mode, and they can reset the password