nimh have a rather flat discharge curve, making it hard to detect their actual state of charge.
A simple solution could involve a current sensing resistor (something small like 100mOhm or 10mOhm to make the math easy), an op-amp and a microcontroller.
The op-amp takes the voltage (which will be positive or negative depending on charge/discharge) and converts to a positive only voltage the microcontroller can understand.
The uC is programmed to count how much time the battery spends charging versus how long it spends discharging (and at what rate). or simpler yet, the uC expects you'll take care of charging and will assume the battery starts each day at 5000mAh. if you worry about discharging only, you can dispense with the external op-amp and just use a diode to block reverse voltage from reaching the pic (be sure to account for the Vf of the diode).
When the uC counts that 4500mAh (or whatever) has been discharged, it can disconnect the load, regardless of the terminal voltage on the battery.
Maxim has some battery supervisor chips that do all this for you - they're fairly cheap, but not easy to work with.