Jailbreaking does not install a fresh copy of iOS on your device, it simply adds on to it. It is, however, recommended that you jailbreak a device that has a fresh copy of iOS on it first, to give yourself a fresh start so not to keep any problems that you may have had in the past.
Try not to use the Settings.app method of resetting your device. In many cases, it can cause major problems or problems that could easily have been avoided when restoring using a DFU mode restore on iTunes. To back up your data, either manually back them up by rooting your device and manually copying and pasting/dragging and dropping to your computer. Or you can sync your camera roll to your iTunes, then perform a backup by right clicking your iPhone's profile on the left-hand taskbar, and click Backup.
If you're looking to jailbreak on a clean copy of iOS 5.1.1, you'll need the SHSH blobs to do so. When restoring to an iOS that's no longer being signed by Apple, you
MUST use SHSH blobs or you can't restore to them. If you don't have blobs, your only available iOS restore is to iOS 6.0.1 for the iPhone 4, which is the latest version. For SHSH blobs, you'll have to manually save them on non-jailbroken iPhones during the open window period where Apple was still signing that iOS, so if you did not save your blobs manually back when iOS 5.1.1 was the latest iOS firmware, you can no longer save them, and your only option is to restore to iOS 6.0.1.
Before we can instruct you on your next steps, you'll have to inform us on which of the following you want to do:
- Jailbreak your iPhone 4 without first restoring to a clean firmware
- Jailbreak your iPhone 4 after first restoring to a clean 5.1.1 firmware
- Jailbreak your iPhone 4 after first restoring to a clean 6.0.1 firmware
Note that for option 2, you'll need blobs. Since you haven't jailbroken before, they won't be on Cydia's server, and if this is the first time you've heard of blobs ever, then you did not save them manually when they were available, so your only options would really be 1 and 3.