Battery charger vs Voltage or neither - They offer accurate power consumption? (mA)
Your theory is a OK, but here are the issues with Ni-MH cells you need to be aware of:  

1.) Whatever the energy (mAh) you put into an Ni-MH, it will have to be around 150% of its rated capacity because its charging efficiency is around 66%-70% (2/3 actually go into the cell, 1/3 is wasted).  

2.) The self-discharge of the Ni-MH cell would not be an issue if you are testing its capacity with a larger current, but with small currents on the order of a few mA or less, the self-discharge rate will significantly skew your results; the lower the load current, the larger the error of your method.
To quote Wikipedia:"The self-discharge is 5–20% on the first day and stabilizes around 0.5–4% per day at room temperature. But at 45 °C it is approximately three times as high."  

There are low self-discharge Ni-MH cells that hold their charge significantly longer, but they have a slightly lower capacity. I think that for your scenario where the power draw is fairly low, their long-time useful capacity would actually turn out to be higher than that of the standard ones, so they would be better for your use (also, the longer periods between charges and thus fewer cycles per year will result in a longer lifetime).
 They retain about 70-85% of their charge after being stored for one year at 20°C, while the regular ones only retain about 50%.


Li-Ion cells are much more efficient - about 95%+ charge efficiency, and 1.5-2% self-discharge per month (vs. up to 30% per month for standard NiMH), but the low self-discharge NiMH batteries now lose only about 0.08–0.33% per month, according to Wikipedia.  
In short, your method might be OK if you used a high-drain load which would discharge the battery within a few hours, but the longer it takes to discharge, the larger the error in your estimated capacity.
The best method is to charge a cell fully (to around 1.5-1.6V) and then discharge at a fairly constant current (could use a resistor while assuming the average voltage of about 1.25V) which would discharge the cell in no more than 3-10 hours down to around 1.0V (~1.0V is taken as empty with no load or very light load, ~0.9V when under some "average" load).  
Another method to use, since you have Arduino devices which "report" voltage(s) is to place a known value resistor (of sufficient power) of a low value in series with your device and measure the voltage across it: the voltage divided by the resistance will give you the current. You would need a voltage source high enough to account for the resistor voltage drop and provide your device with the needed voltage, but you would risk damaging the device. If your Arduino devices can show low voltages (less than 1V), it would help greatly.