Transfer purchases and Syncing: this will allow for you to back up your app store apps, music, and contact information. Right-click your device in iTunes and "transfer purchases" to move any apps that are on the device, that are not in iTunes, into iTunes. Go to the info tab and sync the device's contacts to a third party of your choice. Photos should be backed up manually, if you do not plan to restore from backup, which you shouldn't anyway. Setting up as new is always the best option. Therefor, back those photos and videos up.
Cydia items: backing these things up are possible with PkgBackup, however, I have never used it so I do not know how it works besides the fact that it saves as a contact therefor you should make sure your contacts are saved. You should still write things down manually just in case something doesn't go well.
Restoring: Since you have your SHSHs saved, restoring to any firmware version of iOS 4 is possible. I would recommend to take the device to 4.1, as it has improved over 4.0.x. If you need to unlock, you will be needing to using a custom firmware.
Restoring without unlocking: Simply run the TSS server and then hold shift+restore, then select a stock 4.1 firmware you can download at felixbruns.de. iTunes should restore without any error. If error occurs, usually TU can kick it out of recovery and kick the phone back up.
Restoring with unlocking: You'll need to build a custom firmware. If you have Windows, you can use Sn0wbreeze 2.1 to create a custom firmware for 4.1. All that you are required to do before shift+restoring in iTunes while running the TSS server, is to get Redsn0w 0.9.6b6 and use it to set your phone into pwned DFU mode only. If your device is already jailbroken right now with a non-userland jb (such as redsn0w, blackra1n, sn0wbreeze, pwnagetool) then you can skip the pwned DFU mode step and simply run the TSS server and shift+restore to the custom 4.1 fw.
If you are on a Mac, you may use PwnageTool to do the same process. PwnageTool allows to set your device into pwned dfu when you are ready to restore.
Custom firmwares: If you do not have an official carrier's SIM to activate with, be sure to create the custom fw in expert mode (for either tool, sn0wbreeze or pwnagetool) and select "activate" to hacktivate. If you do have the SIM, in can be inactive even, you should not select "activate".
If you chose to not include "activate", you can simply insert the SIM and open iTunes and allow it to activate the device after you have restored. If you chose to hacktivate, after the restore should take you straight to your springboard.