Maybe a (partial) solution would be to make the batteries taste bad? Some coating on the outside that makes them taste immediately revolting and increases the likelihood of they'll be spit out
I question that.. There are some pretty powerful bitterants available for this sort of thing. You don't need much denatonium benzoate to make something unpleasant to taste, for example: "Dilutions of as little as 10 ppm are unbearably bitter to most humans." https://en.wikipedia.org/wiki/Denatonium
I don't think it necessarily needs to be that messy. It has no smell, and you can buy nail polish that contains the stuff (used to deter nail biting and thumb sucking), so apparently it can be painted on in a fairly durable fashion. Just a dot on the battery case ought to do it.