Finally found baking soda (bicarbonate de sodium.) Got it in France's largest supermarket chain, Carrefour, of all places. The reason I'd never seen it there before is that it's sold as a dental care product, lying between the high-tech, pulsating, wi-fi equipped electric tooth brushes and pick-your-mouth-phobia and chemical-fruit-taste toothpaste. The package says "no colouring added".
My wife says it's the first coin cleaning product I bought that's safe to eat.