Strangely, yes, the battery does have a serial number, but they can't track it. Initially, the authorised distributor here said that since I didn't have a proper receipt they wouldn't do anything, so I contacted Apple Asia-pacific, and they looked at my email which was from the store I bought that supplied at least a purchase order for a battery, and Apple just said they'll give me a new one. that's first class service! They even allowed me to pick it up in Taiwan when I was on holiday. I never had AppleCare.
So yeah, you may or may not be out of luck without out AppleCare, but be sure to take it into an applestore, and they may be lenient. I recall that they ran a diagnostic test, and my battery failed it. Also, my service battery warning was intermittent. After charging it, sometimes it would appear normal for a few days, but revert back. But do check out other options first, such as the SMC reset.
http://support.apple.com/kb/HT3782