I wonder if this might work:
If possible, download the battery's datasheet from the manufacturer. I know that Energizer and Duracell publish these; I don't know about other makers. The datasheet will usually have a chart on it plotting voltage against time for one or a few different loads. Use a resistor network to present one of the given loads. While the battery is feeding that load, read the voltage on the battery. Plot that value on the chart and it should tell you where on the discharge curve the battery is.
I haven't tested that and just thought of it now so I haven't even really looked for holes in the idea. I'm sure there are some but it seems like a good way to get a rough estimate. The flatter the discharge curve of the battery, the rougher the estimate, though--so some battery types would be easier to measure than others if they were somewhere in the middle of their discharge curve.
Torben