Hmm ok, did you hear three chimes when resetting the PRAM? (Just asking...)
Some other suggestions...
Reset the SMC.
Disable the firmware password if set.
If you boot up from some PCIe controller, attach the boot drive to the internal SATA2 controller.
If you are on 10.9, try the update with 10.8 or below.
Try to flash the original 4.1 Firmware from Apple. (Sounds silly, but you never know...)
Remove all "unnecessary" cards.
Get/lend an EFI GPU card.
For now i'm out of ideas, hope you got it working.
Some other suggestions...
Reset the SMC.
Disable the firmware password if set.
If you boot up from some PCIe controller, attach the boot drive to the internal SATA2 controller.
If you are on 10.9, try the update with 10.8 or below.
Try to flash the original 4.1 Firmware from Apple. (Sounds silly, but you never know...)
Remove all "unnecessary" cards.
Get/lend an EFI GPU card.
For now i'm out of ideas, hope you got it working.