Prior to iOS 5 a computer was essential to backing up an iPhone. If you never synced it with a computer you can still back it up to the computer you update with, then restore that backup. Normally the phone is backed up automatically when you start the update process. Did this not happen?
I don't understand why no backup would be saved. If I understand correctly, option 1 offers you the opportunity to backup (not the opportunity to restore from an existing backup).
Anyway, if you cannot save a backup, and you want to upgrade, I suggest taking your iPhone to a nearby Apple Store. They should have everything you need there.