Will that mess up the jailbreak and unlock on a 3GS?
you won't be able to boot up the phone. at all.
you will therefore need to restore, which if done incorrectly could mean that your phone is not unlockable until a new ultrasn0w is released
What do you want to do?
Restore via iTunes (if unlock is unnecessary), otherwise 'rejailbreak' with something like pwnage tool.
when you 'reinstall' iOS, you are effectively formatting the iPhone. Some will say that you should do this via DFU, I have no opinion as to whether DFU is required or not.
No. Pwnage tool unfortunately only works on a mac.
Is unlock necessary?
If you have any friends with a mac, you can ask them to use pwnage tool for you to make a custom IPSW which you can use in windows with redsn0w.
What SHSH blobs have you saved?
restore your phone to 4.0.x through iTunes and TU and that won't muck up the baseband that you must've preserved.
then set up phone as new.
then jailbreak (or upgrade to 4.1 SAFELY without mucking up the Basebandn EDIT: I don't think this is possible at the moment) and unlock.