The magic number for four cells is basically anything over 5 volts. Then connect a heavy load, say a 2.2 ohm 10 watt resistor for a few seconds and check the new voltage reading under load. If a minimal drop is shown (should still be above 5V), there is plenty of life in the battery, but of course the battery is discharging all the time the load is connected.
If using NimHs, no harm is done by recharging early, and the alleged memory effect associated with NiCads is just that in my experience - alleged. Every time I have had a close look at a set of NiCads suffering "memory" it has turned out to be one dud cell in the pack.