LiPo is MUCH easier to manage well than NimH.
Energy densities for top capacity NimH are about the same as LiPo nowadays.
(That was written in 2012. In 2021 LiPo energy densities are now typically somewhat higher).
NimH is a relatively hard battery chemistry to manage well. Charging at low rates is not usually advised and negative voltage deflection under charge or temperature rise are the usual end-of-charge detection methods. In contrast, LiPo is charged at constant-current until a set voltage is reached and then at constant-voltage until current falls to a preset level. LiPo will accept any lower-than-maximum rate of charge if desired, and can be recharged from any state-of-charge with no special conditions. (Handling very low voltage cells is slightly more complex, but all sensible charger ICs handle this - and very low voltage should never be allowed to happen.)
The ONLY reason I would think of using NimH in your context is safety - and if it was my son, I'd consider that I could make LiPo safe enough for him to use. LiPo can "melt down" very enthusiastically with flame, BUT it is extremely rare in practice and taking quite usual precautions should allow a safe result.
I would have no personal concerns over LiPo safety in a competently engineered system.
HOWEVER, NEVER use unprotected LiPo cells if you care about safety. The in-battery protection IC DOES NOT serve the same roles as the charger ICs do. The in-battery ones are just to stop people from doing stupidly dangerous things to the battery. That said, IF your charger is properly implemented, and if there is no chance of short or fire potential then most of the protection circuitry is not needed. I say "most" because, if there is e.g. a catastrophic equipment failure and e.g. a short circuit occurs, the in-cell circuitry will usually open-circuit the cell and prevent a fire.
Using the proper charger ICs should allow a very safe and reliable charger to be implemented.
You do not need gas gauging per se - just low voltage cut-out. If you can stop operation at say 3V / cell, that should be enough.
Protected cells should not cost vastly more. If they do, it MAY indicate that the cheap ones are bad ones. You can get utter junk LiIon batteries (and you'd hope to get a price advantage when buying junk :-) - if you were silly enough to buy them. There are enough reputable brand cells around that buying them probably does not cost vastly more. Ensuring that the cells are genuine is another matter. As a working position I suggest you start by assuming that anything bought from a low cost Chinese supplier is fake or out of spec and THEN try and prove otherwise. (NB: Racism? - definitely not!. It's based on experience - many visits to China and time in factories, etc. China is very, very large and has a vast range of sellers in a very competitive market place. In a casual sale, expect a certain portion of the sellers to be 'dodgy' at best.)
Added:
I was going to come back and mention LiFePO4 - AndreKr beat me to it.
Compared to LiPo, LiFePO4 (Lithium Ferro Phosphate) are safer, longer life and have lower energy density. You can buy RCR123A LiFePO4 batteries with 450 mAh x 3.2V capacity. (Some claim up to about 700 mAh but are suspect.) Tenergy LiFePO4 RC123A are widely advertised on ebay and should be good. Tenergy are AFAIK a "rebadger" BUT seem to sell good product. LiFePO4 MUST be charged properly, but are as easy as LiPo to manage. A very simple charger can be built using a constant-current regulator followed by a 3.6V constant-voltage regulator. This setup charges at constant current until Vlimit is reached, and then at constant V. Setting to 3.5V is better.
Here is a randomly found seller of Tenergy LiFePO4 RCR123A batteries. They also sell chargers.
NOTE:
Do NOT use Lithium Ion RC123 (3.6V nominal).
Do not use 3.0V Lithium Primary RC123.
The terms RC123, RC123A, RCR123, RCR123A etc are used somewhat interchangeably by sellers. Just be sure of what you are getting.
Best Answer
I was actually planning on building one of these. I decided that it would be easiest to start with a USB Arduino to have easy data logging to the PC. I figured I'd use an Uno, even if I wrote the code in native AVR C, rather than Arduino.
For this, you are looking for a constant current sink. Something that will pull a constant current, even as the voltage of the battery drops.
You need two ADCs to measure voltage. First will measure the actual battery voltage. Depending on how accurate you want to be, you can either use the 5V power as the ADC reference or use a more accurate ref chip. You will need some type of shunt to measure current. (A shunt is a known resistance. So by measuring voltage across it, you can know the current flowing through it via Ohm's Law.)
Lets work backwards from the battery. If we have a logic level N Channel MOSFET as a controller and an accurate resistor in series with the Drain/Source. The resistor will work as our current shunt. The battery + connects to the source of the MOSFET, then the resistor connects the drain to ground. The battery - is also to ground. If you have 1 Ohm resistor, and measure 1 V across it, you know that 1 A is flowing through it.
(A Logic Level MOSFET is one that will turn on with a gate voltage in the normal range of logic chips, generally fully on before +5V. It is useful for driving heavier loads from low current capable logic.)
OK, now we need to control the MOSFET. Hook up an Op Amp as a voltage follower, with the + input for setting the voltage (more about that later) and the - connecting to the drain/resistor junction. The output of the Op Amp goes to the gate of the MOSFET. The Op Amp will adjust the gate of the MOSFET, until the voltage at the drain (and across the resistor) meets the voltage presented at the + input of the Op Amp. This means it will consume a variable amount of voltage to maintain maintain a constant voltage across the resistor and therefore a constant current through the resistor. (And a constant current draw from the battery.)
Remember that the ideal Op Amp model is such that voltage between + and - is 0V. In reality, there is a little, but you will be compensating for this so it doesn't matter unless you try to drive it too close to the rail.
So we now have a circuit that will draw a current in amps equal to the voltage in volts that you provide to the + of the Op Amp.
The last things we need is to measure voltage and current and generate that voltage.
You can use the PWM output of the micro to generate an analog voltage. You would hook a resistor in series with the pin and a capacitor from the end of the resistor to ground. This junction will feed the + input of the Op Amp.
Now we need to feed the voltage across the shunt resistor into one ADC input. This will read discharge current in Amps if you use a 1 Ohm resistor. Use this to drive the PWM output until you are pulling the desired current from the battery. It may be better to drive a voltage divider with a trimmer resistor, so you can tweak the circuit to give outputs that correspond to given PWM duty cycles.
The last hookup is an ADC input from the battery itself. If you are using a battery that is over your supply voltage, you will have to use a voltage divider to get it down to a range that the ADC can handle. You may need a switch to have a few different dividers, based on the number of cells you will hook up.
Once you have registered a voltage down as low as the battery should drain, set the PWM output to ground and this will turn the MOSFET off and stop draining the battery.
Add the associated logging to the PC and you are done.
Make sure you get proper power rated MOSFET and shunt resistor. If you are driving 5A through the 1 Ohm resistor, you will need 5W resistor. It might be easier to put a few in parallel to get to the desired value and power. You also need a MOSFET with enough power handling to sink the voltage difference between the battery and resistor at that current. And you will need a good heat sink for running higher power. The MOSFET and shunt are the only parts of the circuit that will be handing large currents. All the others should be fine.
With this circuit, you can use it for more than just battery testing. If you are developing a power supply and want a 1A load on it to see how bad the ripple looks, hook it up. As long as you don't exceed the power ratings of the MOSFET or Resistor and stay within the proper bounds of the ADC inputs, it will work.