Restore it to 3.1.2 and jailbreak with Redsn0w 0.9.4.
Or restore it to 3.1.3 and jailbreak with the same Redsn0w listed above. Just have to point at 3.1.2 ipsw in Redsn0w.
Redsn0w allows a combined jailbreak and unlock for iPhone 2G. So in Redsn0w, be sure to select "Cydia" and "unlock" when prompted. It will auto unlock for you when the jailbreak is done.
You'll also need bootloader files 3.9 and 4.6. I'll be right back to post a full guide with download links included.