20 - 30 minutos
3GS was turning off all the time, more so when I was using GPS or videos.
Repair went fairly smoothly and now my iPhone stays on. :~) Took about 30 mins.
Search youtube for iphone battery replacement, some very good detailed videos out there. just take your time, I had a little trouble getting the logic board seated correctly, don't force it.
A little tip on getting the old battery out, take a moist wash cloth and microwave it for 45 seconds place iPhone on wash cloth to gently warm it, battery should come right out.