try booting into Open Firmware: boot holding Command-Option-O-F.
When you get the OF command line, type
eject cd [press enter]
it should open the tray.
If not, then type:
reset-nvram [enter]
and then
reset-all [enter]
Then try all the things you've already tried again.
(I ran into this exact problem on an old slot-load iMac last week, which is why it's fresh in my mind.)
tooki