If you just want to clean up your hard drive then boot a "Live" Linux CD, like Knoppix. Knoppix runs completely from CD and does not mount your hard drive(s) unless you ask it to. It auto detects everything. I've booted it up on 4 different machines all with varying hardware and it worked flawlessly. After you boot up you will have full access to your drives (to format, repartition, retrieve data, whatever). Once you've booted follow the instructions previously given (see man pages for mkfs and fdisk).
Unfortunately this doesn't really help you install a new OS.
Getting a live CD: Try www.knoppix.org,
download mirrors are about 2/3 the way down the page. Or if you don't have a CD burner then www.linuxcd.org
will sell you one for $1.99. If you have limited internet capability you might try something like "Small Linux" which fits on a floppy (don't know if it has tools to format your drive though)
p.s. However you eventually solve your problem you should burn/buy a Live CD just for emergencies. They're great to have around if something goes wrong and you need to get at your hard drive.