Apple is no longer signing 4.1 for the 3GS as mentioned above. If you used a custom firmware, chances are it's already been stitched. The only way to restore to an iOS that's no longer being signed is to have SHSH blobs. There are no exceptions, no hacks, no exploits, no cheats, no downloads, no backdoors, no workarounds, no rooting, nothing. Nothing that can bypass the mandate for SHSH blobs. If anyone tells you otherwise, they're relaying false information. SHSH blobs are mandatory for restoring to iOS's that are no longer being signed.
Jailbreak the iPhone 3G using RedSn0w's latest version, which is 0.9.15 beta 3. Download the 4.2.1 IPSW for the iPhone 3G, plug the 3G into your computer. Then go to Extras > Select IPSW and point it to the IPSW that you just downloaded. Then click back, and click Jailbreak. Put your device into DFU mode. If you don't know how to, follow the on-screen instructions that'll guide you. Once you approach the screen with a list of tickboxes, tick "Install Cydia" and "Deactivate" (tick Deactivate if you don't have an original carrier SIM for the 3G). Let the jailbreak process. Once you're finished, install UltraSn0w through Cydia and reboot your device. You're now on an untethered jailbreak and unlocked using UltraSn0w.