iPhone 4 4.0 upgrade to 4.3.3, jailbreak/unlock without SHSH files?

A colleague of mine would like her iphone 4 unlocked for when she travels to Asia. She has never upgraded teh phone and it's running 4.0 and baseband 1.59.00

When I bult a custom IPSS using Pwnage tool and tried to install it, iTunes complains that the phone is not eligible for that version (I was using 4.3.3 since that's the last untethered jailbreak for her phone)

I had thought that I could get the jailbreak in but that I was flying without a net and that if she ever had to restore with no SHSH files that she would have to upgrade to whatever is the latest version.

did I get that wrong?

(she reverted back to iOS 4.0 and jailbroke it with jailbreakme.com for now, but would like to upgrade to 4.3.3 to get a couple of things. She's not interested in a tethered 5.0 jailbreak so going all the way to 5.0 with redsn0w and a custom IPSW is not in the cards right now)

Without SHSH, she cannot go to 4.3.3. There is no workaround for this -- she'll need to go to iOS 5 unless she has stored SHSH for any other 4.x versions.