How can I buy a new 8GB iPhone 3GS that still has iOS 4? My contract with AT&amp;T is up for renewal. My wife has an iPhone 3G. I'd like to use my renewal to score her a free upgrade to a 3GS.

She's on T-Moble and so needs to have her phone jailbroken and unlocked. 

I read that all new 3GS models are now bundled with iOS 5. 

How can I buy a new 8GB iPhone 3GS that still has iOS 4?  Is the packaging any different?  Are there any telltale signs that indicate firmware version before purchase?
Firstly im not sure the phone needs to be jailbroken and if a contract is up the carrier is required to give instructions on how to unlock.

The packaging is not different.

Not all 3GS models are bundled with iOS5. I would look at some websites that do not sell a lot of these phones, ask shops how long they have had the particular model in stock, if the had them for over 2 months then you're in luck.

You could also look to buy a second hand model, which hasn't had an update.

Can I ask why you do not want iOS5?