It shouldn't be all that bad. 4 or 5 volt NiMh or NiCd packs are fairly inexpensive compared to your probably overall expense so far. I would opt for a 5 cell of around 1800 mah capacity. I would advise you to stay away from a regulator.

CGr