Is it possibe to upgrade and re-jailbreak (in order to unlock) a 3Gs running on 4.1?
You're a few weeks too late.

There was the Evasi0n jailbreak, which worked on iOS 6.0 - 6.1.2, but iOS 6.1.3 killed it.