How do I check to see if a nonrechargeable battery obeys the law of conservation of energy?

I don't think it's experimentally feasible, but if one could measure its change in mass precisely enough, it will change by $1/?^2$ times its change in potential energy, which will will be the energy produced during discharge.

If you discharged it through a resistor, then the total energy as heat generated by the resistor (plus any other small effects like battery heating or work done by the magnetic field generated by the current loop) will be equal to $Delta m c^2$.

Wikipedia's Comparison of commercial battery types; common characteristics suggests that the old zinc-carbon batteries stored about $10^5$ joules per kilogram. The energy equivalent of that energy is $10^{22}$ joules, so you'd have to measure the change in mass to a relative precision of $10^{-18}$ in order to get a confirmation of energy conservation to a level of 10% which doesn't sound feasible to me at least ;-)

This will provide an upper bound:

1. Measure the mass of the battery.
2. Count all the atoms in the battery (good luck!).
3. Compute the mass of all the atoms under the assumption of the atoms are non-interacting.
4. Since E=mc^2, the difference between the actual mass and the computed mass is an upper bound on the potential energy that could be discharged from the battery.

If discharging the battery produces less energy than this upper bound, that is evidence the battery is consistent with the law of conservation of energy.

Your options are limited because the one thing you are choosing to exclude from your list of options is actually measuring the energy. Measuring the energy must be done by transferring the energy from one form to another. (Or some crazy relativistic stuff that will not work on any batter with less energy than, say, a large star)

The closest I think you can get to your ideal is to take the battery apart, measure the mass of the electrodes and electrolytes, and look up on a table how much energy would be stored there. You might try using a small portion of the material, discharging it, and extrapolating.

The easiest solution would be to buy two identical batteries, and discharge one, measuring it's stored energy. Then you can make inferrences about how much energy is in the second.

All that being said, if you are exploring whether energy is being conserved or not, what you actually need to do is look at the process used to construct the battery, not just the final product. If you could create a battery using less energy than it stores, then you would violate the conservation of energy. Conservation of energy does not specify a maximum energy density, nor does it specify what form of energy is in use (your self-answer points out how much energy can be released once you consider nuclear or direct energy conversion).

With all of those practicalities, batteries are actually not the right place to explore conservation of energy. They are far too messy, and they're actually so far from 100% efficient that it's hard to even meaningfully talk about them in terms of conservation. I don't have any hard numbers, but I'd hazard a guess that the process of creating a battery is no better than 10% energy efficient. There are other processes (especially those involving superconductors), where we can talk about 99.99% efficient energy transfers and decide how many nines we want. They prove to be a much more suitable place to explore.