Upgrading an ancient 3gs running on 3.13 - can u guys help me out please??

[King Candhi]

Hey guys Im hoping someone here can give me some clarity with a jailbreaking prob Im having..
okay so I researched a little before i posted but forgive me cuz i know im asking a question thats been asked a million times on here.. Im hoping someone can help me out tho..
So I already have a jailbroken 3gs thru spirit i believe, but its still on 3.13.. so now that almost every app is starting to need 4.0+ im hoping to upgrade my firmware..
so i was hoping to go the simplest route and go thru jailbreakme.com, but since im still jailbroken i know i shouldnt use that method with my specs right now, unless i want to destroy my phone...
so my question is if I download a random custom ispw like 4.21 or even the newest 5.0 and restore to it thru the dfu mode with itunes, after i restore, will i b able to just go back into jailbreakme.com and it should work okay now?.... or is there a certain ispw i have to d/l because im still on 3.13 to use with jailbreakme.com??
What really confuses me tho lol is the SHSHs. I dont have any saved right now - do i need to d/l tiny umbrella and save those or can i get around it just by restoring to a custom ispw??
also I use other methods besides itunes to get my music and stuff on/off my phone, i realize i need itunes to restore, but is there a certain version i need to use or is the newest one okay??

Id b really appreciative of any help you guys can give me, or if theres an even easier solution - im totally stuck!

thanks guys,
peace

[b0bab0i]

Do you need the phone to be unlocked?