Assuming you can boot from the Leopard disc, it should work.
You can boot from the install disc by holding C during boot.
To boot the computer, you need an already-formatted disk, which could be a DVD, a USB drive, or another hard drive.
If you do not already have one of these (and do not have another Mac that you can use) then your options are fairly limited:
Buy Snow Leopard on DVD. You can get it from Apple for $30, free shipping, but it won't ship for 3-5 days.
Buy DiskWarrior [$100] which is probably your best bet if you want to try to save the current hard drive.
Buy Lion on a USB drive $70 from Apple. Note that this is a terrible solution, IMO, because you will not be able to download Lion from the Mac App Store nor will you be able to use Lion's "Recovery Partition" (which, if you had it on your Mac, would most likely have solved your problem).
The rest of this answer is strictly opinion.
Personally I think your best option is #2 and #1.
DiskWarrior is an essential tool for trying to recover from hard drive errors. If your drive is having problems, I would not trust it for very long. Copy an essential files to another drive and then run DiskWarrior. Even if DiskWarrior is able to correct its errors, I would be sure to start making regular backups using either SuperDuper or CarbonCopyCloner.
The problem is that if DiskWarrior finds problems that cannot be fixed, then you are going to need to replace the hard drive and reinstall Mac OS X… which means that you are going to have to buy Snow Leopard on DVD (assuming that you don't have a friend who can make or loan you a copy).
The $70 USB stick from Apple is a terrible deal. If you want to move to Lion, buy your own USB drive, find a friend with a Mac, ask them if you can use it to buy Lion from the Mac App Store, and make your own Lion USB drive using one of the many how-tos posted online, such as this one from TUAW.com.
Best Answer
How do you know that your file's permissions are not OK? What output does your repair permissions print? Any errors?
You could also try running the repair from the command-line if it would make any difference:
diskutil repairPermissions /Volumes/Macintosh\ HD/
Replace the volumes name.
You could also try running that with sudo or as root, to see if it changes anything.
Edit: Actually, what you could be seeing is that some application is using the files that "need" to be repaired and thus Disk Utility can't repair them.
Try shutting all applications off and the running the repair