Here's your problem, in a nice graphic from Battery University. Most battery chemistries in use today (Li-whatever, NiCd, NiMH, lead-acid) have a discharge curve that features a short downward drop in voltage, a long nearly-level voltage vs. charge section, then a "knee" leading to a quick drop-off.
To complicate things:
- the cell voltage is often more sensitive to the current draw than to state of charge
- the cell voltage is sensitive to temperature
- the cell voltage, and it's drop-off is sensitive to construction and chemistry details of the cell
- the cell voltage is sensitive to aging in hard-to-predict ways (basically, as it ages its "chemistry and construction" change).
This means that any attempt to determine the battery's capacity before it hits that knee in the discharge curve is just guesswork, and probably bad guesswork.

There have been attempts made to determine state of charge by drawing a pulsed current from a battery, because a cell's internal resistance also depends on the state of charge (this is more or less the reason that you have different discharge curves in the graph corresponding to different discharge currents). But a cell's behavior in this regard is also dependent on temperature, construction, chemistry, aging, etc. So that doesn't work well, either, except perhaps as a route to a PhD for someone who wants to get a job designing batteries.
Bottom line: you'd be better off determining its general chemistry, weighing it, and multiplying that by some constant that matches its chemistry -- you'd still be wildly wrong, but you'd be less wrong than trying to do it by discharging and watching the voltage, and it'll take less time.