Here are a few ways I can think of, from the least intrusive to the most intrusive.

Without Rebooting

With sudo: if you have sudo permissions to run passwd, you can do:

sudo passwd root

Enter your password, then enter a new password for root twice. Done.

Editing files: this works in the unlikely case you don't have full sudo access, but you do have access to edit /etc/{passwd,shadow}. Open /etc/shadow, either with sudoedit /etc/shadow, or with sudo $EDITOR /etc/shadow. Replace root's password field (all the random characters between the second and third colons :) with your own user's password field. Save. The local has the same password as you. Log in and change the password to something else.

These are the easy ones.

Reboot Required

Single User mode: This was just explained by Renan. It works if you can get to GRUB (or your boot loader) and you can edit the Linux command line. It doesn't work if you use Debian, Ubuntu, and some others. Some boot loader configurations require a password to do so, and you must know that to proceed. Without further ado:

1. Reboot.
2. Enter boot-time password, if any.
3. Enter your boot loader's menu.
4. If single user mode is available, select that (Debian calls it ‘Recovery mode’).
5. If not, and you run GRUB:
   1. Highlight your normal boot option.
   2. Press e to enter edit mode. You may be asked for a GRUB password there.
   3. Highlight the line starting with kernel or linux.
   4. Press e.
   5. Add the word ‘single’ at the end. (don't forget to prepend a space!)
   6. Press Enter and boot the edited stanza. Some GRUBs use Ctrl-X, some use b. It says which one it is at the bottom of the screen.

Your system will boot up in single user mode. Some distributions won't ask you for a root password at this point (Debian and Debian-based ones do). You're root now. Change your password:

mount / -o remount,rw
passwd # Enter your new password twice at the prompts
mount / -o remount,ro
sync # some people sync multiple times. Do what pleases you.
reboot

and reboot, or, if you know your normal runlevel, say telinit 2 (or whatever it is).

Replacing init: superficially similar to the single user mode trick, with largely the same instructions, but requires much more prowess with the command line. You boot your kernel as above, but instead of single, you add init=/bin/sh. This will run /bin/sh in place of init, and will give you a very early shell with almost no amenities. At this point your aim is to:

1. Mount the root volume.
2. Get passwd running.
3. Change your password with the passwd command.

Depending on your particular setup, these may be trivial (identical to the instructions for single user mode), or highly non-trivial: loading modules, initialising software RAID, opening encrypted volumes, starting LVM, et cetera. Without init, you aren't running dæmons or any other processes but /bin/sh and its children, so you're pretty literally on your own. You also don't have job control, so be careful what you type. One misplaced cat and you may have to reboot if you can't get out of it.

Rescue Disk: this one's easy. Boot a rescue disk of your choice. Mount your root filesystem. The process depends on how your volumes are layered, but eventually boils down to:

 # do some stuff to make your root volume available.
 # The rescue disk may, or may not do it automatically.
 mkdir /tmp/my-root
 mount /dev/$SOME_ROOT_DEV /tmp/my-root
 $EDITOR /tmp/my-root/etc/shadow
 # Follow the `/etc/shadow` editing instructions near the top
 cd /
 umount /tmp/my-root
 reboot

Obviously, $SOME_ROOT_DEV is whatever block device name is assigned to your root filesystem by the rescue disk and $EDITOR is your favourite editor (which may have to be vi on the rescue system). After the reboot, allow the machine to boot normally; root's password will be that of your own user. Log in as root and change it immediately.

Other Ways

Obviously, there are countless variations to the above. They all boil down to two steps:

1. Get root access to the computer (catch-22 — and the real trick)
2. Change root's password somehow.

Sudo, in its most common configuration, requires the user to type their password. Typically, the user already used their password to authenticate into the account, and typing the password again is a way to confirm that the legitimate user hasn't abandoned their console and been hijacked.

In your setup, the user's password would be used only for authentication to sudo. In particular, if a user's SSH key is compromised, the attacker would not be able to elevate to root privileges on the server. The attacker could plant a key logger into the account, but this key logger would be detectable by other users, and could even be watched for automatically.

A user normally needs to know their current password to change it to a different password. The passwd program verifies this (it can be configured not to, but this is not useful or at all desirable in your scenario). However, root can change any user's password without knowing the old one; hence a user with sudo powers can change his own password without entering it at the passwd prompt by running sudo passwd $USER. If sudo is configured to require the user's password, then the user must have typed the password to sudo anyway.

You can disable password authentication selectively. In your situation, you would disable password authentication in ssh, and possibly in other services. Most services on most modern unices (including Ubuntu) use PAM to configure authentication methods. On Ubuntu, the PAM configuration files live in /etc/pam.d. To disable password authentication, comment out the auth … pam_unix.so line in /etc/pam.d/common-auth. Furthermore, make sure you have PasswordAuthentication no in /etc/ssh/sshd_config to disable sshd's built-in password authentication.

You may want to allow some administrative users to log in with a password, or to allow password authentication on the console. This is possible with PAM (it's pretty flexible), but I couldn't tell you how off the top of my head; ask a separate question if you need help.