IPhone – Never backed up to iTunes or iCloud. Recovery mode

I don't have a great answer - but this is fairly serious so I'm going to start an answer and hope someone else edits or answers if they can spot something I haven't.

On the computer, the only "red flag" would be if you wiped the phone of all content and settings, named it exactly the same name as it was before (which could be iPhone) and then backed up again and overwrote the backup with the actual data. iTunes tries hard to prevent this and spawn off a date-protected backup when it detects this, but I've seen this check fail and people lose backups from time to time. The remedy here is to restore the PC from a backup that has whatever MobileSync folder is the most recent.

On iCloud - you also shouldn't be able to overwrite a "full" backup with an empty one. Also, iCloud explicitly keeps several versions of the backups going back in roughly day intervals. It also normally stores backups for different devices without collisions or overwriting another backup.

The good news on iCloud is you can always get help from Apple at http://www.apple.com/support/icloud/ and from retail stores. New devices or ones covered by Apple Care also have phone or web support in most countries. All new Apple products have a 90 day window of set up help. Hopefully one of these can step in and assist. Not only does Apple get a data point where their tools let you down (and exactly what circumstances this happened) - they also see many people in this situation and will hopefully waste a minimum of your time getting this sorted.

You may be stuck on iOS 7 if you don't have a way to get that software from Apple's servers. Typically only registered developers can download several versions of software, but if you search - there are many places that archive these software ipsw files. It's always a bit of a risk downloading software from a place other than the vendor, but I don't know of a better option.

Typically, when a new OS is released, iTunes will only download the latest software if you don't already have an older version of the software stored locally. Is there any chance that computer (or another computer) downloaded iOS 6 and still has it on the hard drive? If so, you can decline the offer to upgrade and restore the device from that version of firmware.

As was covered in the comments - there is no restriction to load iOS 6 backup on iOS 7. Also - this is more about the computer and iTunes having the old iOS file already downloaded than something that's inherent on the device. Any change you have a backup copy of the iOS files iTunes downloaded?