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.

I totally agree this is a bad thing to do. But it can be done in debian by doing as you have done passwd -d root to clear the password then editing /etc/pam.d/common-auth. Find the pam_unix.so line and add nullok to the end if its not there or change nullok_secure to be just nullok if yours says nullok_secure.

This works on Debian Wheezy (and Squeeze).