20 - 30 minutes
The iPhone 3GS of my wife had problems with the battery. In Brazil, replace battery costs is $250.00 on a Apple Authorized Service Provider.
It was pretty easy to replace the battery following the iFixit guide. I spent 30 minutes of my time. The guide is very complete.
I had difficult to pull up the bottom portion of the iPhone's display assembly and to remove the battery that is glued. Keep calm.