Update iPhone 4S before activation
You are forced to activate the phones OTA or via iTunes before you can sync apps over the 30 pin connector or access iCloud or the App Store on iOS.

You can put the devices into recovery mode and update the OS from iTunes to get part of the way there.

Just because you're a windows shop, don't assume you won't come out ahead getting the configurator and a computer to use as an appliance for saving you valuable time in setting up the devices your employees are using. I understand not wanting to fight a battle with limited time, but this might be a nice time to branch out and come out ahead in experience and tools.

If I were in your situation, I would have each employee make iCloud and ensure the device is backed up to iCloud to do the migration. You can be there to guide them, but they are responsible for moving their data and settings to their new devices. (Your comment about data privacy means iCloud is clearly not something you want so I understand that with sensitive data but perhaps others can rely on that when they have a similar problem)

You can update all the new devices to iOS 5.1.1 and they can get help from you if they can't get their devices up to that level or backed up before they arrive for their exchange.