That's really strange. No internal CD, and it can't boot from the drive... I guess Sony wants you to pay for service. That sucks.
If all else fails, maybe you can open the case up and hook up both the HD and a non-USB CD drive. Just leave the case open while you reinstall.
Or... install a Linux distro from a floppy.