My 23 month old iPhone 3GS would shut off randomly and then show no battery. Sometimes I could turn it back on and the battery would be about 50%. So I'd plug it in and within minutes it would back up to 100%. Then a few minutes later, it was off again. This happened on 3G, wifi, phone call, Safari, games, with all the bells and whistles turned off, etc. I spent weeks researching the web and found one post about replacing the battery. I just wanted my iPhone to last until the 5 came out. Since the genius bar fix (back up, synch, restore, etc.) didn't work, I gave this a try. ifixit.com sells OEM batteries and a replacement kit for about $30. The directions were very complete (except connector 5 was a little more difficult than I was expecting). I was very nervous about doing this but figured the phone was useless to me anyway, so why not. Amazingly, when I got it put back together, everything worked and the phone functioned just like it did when it was new. This was about 3 months ago and everything is still working. And I haven't had to turn off all the features I got the phone for, either. There are other companies that sell these kits but ifixit.com has a great reputation.
If you do this, MAKE SURE YOU GET THE RIGHT BATTERY. You cannot use any other battery other than the OEM one. And don't be discouraged if it doesn't work. There was a bad batch of batteries a few months ago. ifixit.com will immediately replace whatever they sent you.
Lately I've been reading posts complaining that this only started happening after one of the 4.x upgrades. I found a few answers about one of those upgrades not being compatible with the original battery. So if your 2 year old iPhone 3GS is shutting off randomly and the battery meter is funky, or this just started happening, try replacing the battery.