Restore iPhone 3GS without backup
If you setup your phone to use iCloud, it is easy to restore.  My wife broke her phone and when the Apple store replaced it everything was easily setup and downloaded via iCloud.

Because at this point I don't know if you ever backup up via iCloud, I will provide directions in case you have... hopefully, you did.

http://support.apple.com/kb/HT4859

If you didn't, you should do it moving forward ... it is never to late to learn from something like this.
Turn on iCloud follow the steps, try to normally connect to a wireless router and from now on make sure to backup via iCloud.