Same issue I had. My friend had just replaced her iPhone with a version 5 and two days later needed to download the old iPhone 4 - but somehow the battery completely and utterly failed in those two days - shady...
Anyways, I did a quick search online and found that it's quite easy to avoid the $79 Apple fee and get a new battery online. Overstock dot com sells them as do lots of places (~$12).
iFixit.com doesn't sell the battery, but they sell the iPhone 4 Liberation Kit - which is useful if you don't own a tiny Phillips-head screwdriver. You'll possibly need the pentalobe screwdriver, but not necessarily - check. Even if your external screws are the weird pentalobe-head, the internal battery screw will be tiny Phillips.