Yes, you can upgrade to 5.1.1 but you need to preserve yor Baseband from 4.1 during the process.
Download latest redsn0w from here:
http://blog.iphone-dev.org/
Download 5.1.1 IPSW for the 3gs from here:
http://m.iclarified.com:8080/entry/index.php?enid=750
Make a custom 5.1.1 IPSW with Redsn0w, it will look like NO_BB...
Download TinyUmbrella from here:
http://thefirmwareumbrella.blogspot.nl/
Connect phone to USB
Open TU, go to advanced tab an UNcheck set host to Cydia. Close TU an restart computer if a windows machine.
Now with the NO_BB custom 5.1.1 IPSW in iTunes select ALT-restore(mac) or SHIFT-restor(win) and restore with the custom NO_BB ipsw.
Afterwards you will have a 3gs with 5.1.1 iOS and the 4.1 BB, phone will not activated.
Now jailbreak with redsn0w and during the process it will ask to activate the phone, do so.
On your jailbroken and activated phone install ultrasn0w in Cydia and reboot phone, phone should now be working.