The iPhone 3GS and 4 can always be jailbroken on any iOS with RedSn0w, it's just a matter of whether it's tethered or untethered. For iOS 6.0-6.1.2, the iPhone 4 can be untethered jailbroken using Evasi0n. On iOS 6.1.3, you'll only have a tethered jailbreak using RedSn0w. If you don't have blobs, you can't selectively restore a device to an iOS as explained here.