How to boot into the EFI firmware shell

The boot selector scans all possible boot devices, including network, firewire, and USB devices. Try disabling WiFi, unplugging everything, resetting PRAM (like cksum said) and then rebooting again. The fewer choices the boot-loader has, the faster it will load. The ultimate speed up, is to go into System Preferences -> Startup Disk to select the desired partition. It sounds like that is not what you want, but it illustrates the process.

If you can successfully start your Mac from a Mac OS X DVD take a look at this: http://pubmem.wordpress.com/2011/04/09/flash-efi-firmware-update-manually-on-a-macbook-51/, especially comment 54 and follow-ups.

It explains how to manually flash the EFI firmware:

1. Download the EFI Firmware update from Apple. This link lists EFI and SMC firmware updates. You will need the exact model identifier of your Mac.

2. Unpack the firmware pkg using unpkg. You will need access to a Mac for this, as unpkg only runs on OS X. You need the file with extension scap.

3. Start your Mac from a DVD and select Utilities>Terminal.

   Now comes the difficult part. You need to run this:

   sudo bless -mount / -firmware /path/to/your/firmware.scap
   

   It is unclear to me whether / is the right path (as asked in comment 59) or if you can even access the internal harddisk when booting from a DVD. You may have to plug in an external drive and copy the scap file there... You will have to figure it out for yourself.

   Alternatively, you can try:

   sudo bless -device /dev/disk1 -firmware /path/to/your/firmware.scap
   

4. Restart. The Mac should flash the EFI firmware.

Disclaimer: Be aware that I couldn't test any of this so I'm giving the following information as a hint in the hope that it is useful.