You didn't say what your OS version was, but if it is pre-lion, I have heard that you can call Apple and get them to send you a DVD. Can't say this is the absolute truth - just going from memory.
You could clone your startup disk to an external drive using SuperDuper! or Carbon Copy Cloner, then boot from the external to repair the startup disk with DU.