Great batteries to use are lithium ion, as already mentioned by Kendall here,
10440 Li-ions are exact size of AAA, but instead of 1.5 V each, they carry 3.7V each, 4.2V when fully charged.
14500 is size of AA.
So you can get ordinary hosts and use lithium ion batteries to get needed voltage when running linear regulators like RCKSTR driver or homemade LM317/350/1117, or whatever you use.
You can get batteries cheap at DX:
10440 :
DealExtreme: $4.23 Ultra Fire 10440 3.6V 500mAh 2Pack
14500 unprotected:
DealExtreme: $3.99 TrustFire 14500 3.7V 900mAh Rechargeable Lithium Batteries (2-Pack)
14500 protected:
DealExtreme: $4.73 TrustFire Protected 14500 3.7V 900mAh Lithium Batteries (2-Pack Blue)
There are also protected 10440 but I have not tried them out myself, but AFAIK they will not fit in some 3xAAA holders.
Also, difference in protected and unprotected:
Protected batteries have a small regulation circuit on round thin PCB on their negative end, the circuit monitors the batteries voltage and when voltage reaches critical discharge limit, which is 2.75 for li-ion chemistry batteries , it will shut off the battery to prevent damage.
Also can protect against short circuit and overcharge but that is not as neccesary.
EDIT - Oh I'm sorry I forgot the chargers:
http://www.dealextreme.com/details.dx/sku.4151 this one has sliding contacts and will charge almsot all batteries between 10440 and 18650, however it's sold out so I think this:
http://www.dealextreme.com/details.dx/sku.12594
Is exactly the same but black color.