Guidance for Jailbreaking/Unlocking iPhone 3G

[ModusOperandi]

I recently came across a (physically) broken iPhone 3G. I've done all the necessary repairs and now I want to jailbreak it and potentially unlock it. I used to have a jailbroken iPhone 3GS so I know how to jailbreak in general, but I'm wondering what my best option is with this device.

The iOS version is 3.1
BB is 05.11.07-5.9_M3S2

Using tinyumbrella I was able to create 2 shsh files, one for 4.1 and one for 4.2.1. AFAIK this phone has never been jailbroken before.

What is my best option here? How far do I update before jailbreaking/unlocking? Or should I get all of that out of the way before any upgrades? I've tried to use jailbreakme but apparently my software version is too old to use that anymore. So in that case, what tools are my best option. I have OSX and Windows available to me so any tool is good.

Thanks in advance.

[iYeow]

You can create a custom firmware of 4.2.1, put iphone into pwmed dfu and restore to cfw of 4.2.1