Sorry, I can't add comments yet. But instead of trying to measure the battery capacity, why not simply measure the battery voltage?
For example, an AA Alkaline Battery has something around 2500mAh and their initial voltage will be just below 1.6V when brand new. You could simply assume they're 95% empty when they reach 0.9V. Here the datasheet from a Duracell AA: http://ww2.duracell.com/media/en-US/pdf/gtcl/Product_Data_Sheet/NA_DATASHEETS/MN1500_US_CT.pdf as an example, it should be very the similar for other brands.
Using the voltage you can tell approximately how much juice still left on the battery. If you want be more precise, just pay attention to the discharge curve, for Alkaline for example it has a quick drop from 1.6V to 1.4V, than a slow drop down to 1.2V followed by another quick drop to 0.9V.
Rechargeable AA batteries might have a different discharge curve (http://www.fenixtactical.com/manuals/sanyo-eneloop-aa-manual.pdf). As I can't think of a good way of detecting the battery chemistry, you could provide a dip-switch to specify the type or detect the voltage as soon new batteries are inserted and "assume" its chemistry.
At the end, just make a simple table containing: chemistry | voltage | %
Hope it helps!