Skip the next paragraph for the actual tutorial! Its just a boring story any ways.
I have recently gotten an iPhone 3G which had no save SHSH stuck on 4.2.1. The guy that gave it to me forgot the password and before I knew that I had already jailbroken it an unlock it, easily. After finding out he had a password I tried restoring with iTunes but it obviously gave me an error, 1015. I tried redsn0w and jailbreak it again but still the same. I also tried tiny umbrella but still no luck. Finally I tried restoring with custom and it worked.
Original Firmware 4.2.1. Link for any original firmware
Here!
You also need redsn0w! Which you can get
here!
oh! and obviously iTunes!
First step download the custom firmware, redsn0w and iTunes.
Second you have to put iPhone 3g to DFU mode. Instructions
Here!
Third open up redsn0w and browse for 4.2.1 original firmware.
Fourth click on PWN DFU MODE! Wait.......
Fifth Open up iTunes, your iPhone should show up.
Sixth Hold Shift on your keyboard while pressing restore on iTunes. Wait......
Seventh when it is done open cydia and do updates, then you can search within Cydia, "Ultrasn0w" to unlock your iphone 3g w/ baseband 6.15.
Enjoy!