You have a couple of options. If you have the latest version of OS 9.2 installed (and you can boot off of it), the copy of Disk First Aid in the Utilities folder does the same thing. If you want to (or need to) do it off of the OS X Installation CD, boot up as you are. Once in installation mode, go up to one of the menus on the left (either the Apple menu, Application menu, or File menu), and there is an option to open Disk First Aid. You should be able to go from there.
This I can not help you with. You will need another hard drive partition you can boot OS X off of (unless someone's figured out a way to make OS X bootable CDs). Another option is using Norton Utilities 6 in OS 9. That's about all I can think of.
If you have two macs, you can put the busted one in firewire disk-target mode (hold down T at startup) and connect a mac running 10.0 with a firewire cable. It will make your old mac look like a external firewire drive. This will alow you to access the busted mac's hard disk and run drive 10, just select the busted disk in repair screen and enjoy. Good Luck!