Q: Old mini iPod (4GB - year 2004)

You can do it yourself, if you're good at taking apart small gadgets.  Well, it's not actually that small if it's an iPod mini (compared to more recent iPods).  This web site has repair guides

https://www.ifixit.com/Guide/iPod+Mini+Battery+Replacement/411

However, you'll cause some ugly damage if you remove the while plastic end pieces as shown.  I recommend using this special tool sold by OWC

http://eshop.macsales.com/item/NewerTech/TOOLISESAMO/

It is thin enough to easily get between the plastic and metal seam, and flexible enough to pry it off without causing damage.  After creating a gap, you may want to insert a plastic tool to do the rest of the prying.  Those end pieces are clipped AND glued in place; work slowly and patiently.  You also need a small screwdriver to remove a few screws.  The battery has a detachable connector (no soldering skills needed).

The battery part is available from the usual online sources (such as Amazon and eBay).  Here's one on Amazon

http://www.amazon.com/Insten-1300mAh-Battery-Screwdriver-iPod/dp/B004I4ZZU4

Looks like OWC still sells it too (and they have a HOW TO video linked to the product description)

http://eshop.macsales.com/item/NewerTech/BIPOD650MM/

If you don't want to DIY, Apple will not service an iPod mini (too old).  However, you may find an independent electronics repair shop in your area (with Apple expertise) that can do the work, with an Internet search.

Extra NOTE (in case you want try when changing the battery OR for future reference if your iPod mini's hard drive fails)...  You can replace the tiny micro hard drive in the iPod mini with a commonly available Compact Flash card or SD card (on an adapter).  Compact Flash card does not require any adapter, because the stock "micro drive" is the same size as a Compact Flash card (CF card is thinner) and uses the same connector.  SD cards are usually cheaper, but you need an SD-to-CF adapter like this one

http://www.amazon.com/Digigear-Extreme-Ultimate-Compact-Adapter/dp/B00EPMWT1M

I used this adapter to put a 64GB SD ("SDXC") card in my iPod mini, and it works great...