No bootable drive:
To launch the installer, I booted from an external FireWire drive. This means that the installer will create a file named boot.txt for the Open Firmware on the drive the Mac was booted from. The issue is that the Open Firmware is instructed to read this file during the boot process, but it looks for it on the internal drive. So the first boot will fail, as it will not find the file boot.txt. Continue the boot by typing mac-boot while in Open Firmware as indicated by Open Firmware.
Once booted, copy the file boot.txt from the root of the boot drive to the root of the internal drive: cp /boot.txt /Volumes/myVolume/boot.txt. Now relaunch the installer and you are done.
Broken DVD drive:
My internal DVD Player is getting errors on the Leopard DVD, even thought the disc is clean. So I needed to boot from an external DVD player. Pressing the C key at boot did not help. The trick is to set the Startup Disk in System Preferences to the Leopard DVD inserted in the external DVD drive. Then launch the installer, and tell to the Mac how to boot by pressing keys at boot time. During reboot press any key and the Mac will boot on the disc selected in the Startup System Preferences panel.
[robg adds: This hint contains another solution.]

