So, after a long time of tinkering I finally got it working.

Get 4.0 (stock 8A293) on your iPhone
Run redsn0w 0.9.5b
Be patient!  - This took a bit for me. Once redsn0w says it's done, the screen on your iPhone will display what it's doing (flashing NOR) and a running pineapple(?).  
4.0 seems to run faster on my 3G than 3.1.3.

Tried to make this post quick as I'm off to bed!