Single User/Rescue mode for the win.

Maybe, boot into a live CD and chroot the root directory, and then change the password that way?