Ok, primero el iPhone 3G no necesita de SHSH asi que puedes actualizar a 4.x, pero ya estas en 3.1.3 pero el original, ahora haz el jailbreak con Redsn0w [Sólo los usuarios registrados pueden ver los enlaces. ]

abre el redsnow y pulsar en “Browser” y se selecciona el Firmware 3.1.3, descargado en nuestro Pc ó Mac (se buscará a través de la ruta donde se guardó).

Seleccionar install Cydia .

Luego te pedira que apagues tu iPhone y das next te pedira que hagas unos pasos, Los pasos siguientes son rápidos. Si se hacen mal no pasa nada se puede volver a empezar sin problemas. Más que contar el tiempo seguir el movimiento de la evolución de cambios en la pantalla.

Pulsar el botón de “apagado”.
Sin soltar este botón hay que pulsar el botón “Home”. (Home + Encendido-apagado).
Soltar el botón “apagado”.
Empezará a trabajar solo y ya se suelta el botón Home.
Lo anterior hazlo pero con el tiempo que te dice el programa, si lo hicistes bien te hara un proceso, y cuando acabe ya podrás entrar al springboard con cydia instalado y todo :D luego solo vas a cydia, buscas ultrasn0w y lo instalas y ya lo tienes liberado