I backup to iTunes on the Mac. I've still got the version of iTunes that has the app store in it, so have local versions of apps that restore from there. But I'm sure we restored my wife's phone from the Mac Mini that has the latest iTunes sans app store.
I started with a 1st gen iPod touch and each device from then on has been restored from the last backup of the previous device. I've not lost data in apps that I can remember. Just checked, I've still got the SMS messgaes from before I bought this iPhone so they must've come across with the restored data.
Generally, stuff that is created by the iOS device be sure you've got that saved elsewhere (just in case). I use cloud/DS storage for this. Photos are sync'ed back to the Mac via iCloud camera roll and iTunes sync for the camera videos. Also, Moments app does this.
Nowadays iOS apps can be deleted and their data settings are retained so will be there if you reinstall them ... this is how iOS manages storage and offloads apps that aren't being used much (I don't have this enabled).