A software unlock may not work but you can purchase a hardware unlock which will leave it unlocked permanently. Your carrier may also unlock it for free if you ask
Not much into jailbreaking myself, but an iTunes error 3194 means that your device is "not eligible" for the requested iOS build... so do you have the SHSH blobs saved for this version? If Apple is no longer signing that version and you don?t have the SHSH blobs saved, I don?t think you can get there from where you are.
I believe that for the iPhone 3GS, the latest version of iOS is 6.1.3... and if you upgrade, you have to go to that one (without having SHSH blobs saved for an earlier version).