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!