The charcoal connection is found with the ‘Bougnats of Paris’. From France écotours:
in the 18th century, the agricultural crisis forced thousands of French countrymen to leave their homes in search of work. The Auvergne people left the volcanic soil of their homeland for the capital. There, the new Parisians built a community where they became known as “Bougnats”.
The nickname Bougnat first appeared during the Second Empire (1852-1870).The word is a contraction between charcoal maker, charbonnier, and a person from Auvergne, Auvergnats: charbougnats.
At the end of the 19th century, the Auvergne residents decided to sell the coal they imported from Brassac-Les-Mines via rivers and canals. It was at this time when coalmining activity increased that the nickname Bougnat emerged. Immigrants opened Wines and Charcoal cafes to market their commodity, additionally selling spirits and lemonade.
The term “bougnat” then ended up referring to both the Auvergnat residents in Paris as well as their cafes adjacent to their sale of coal. In these particular cafes, women were responsible for serving coffee while their husbands delivered coal to the customers. Often, Bougnats supplemented their activity with restaurants and hotels.
In the Wikipedia entry for Bougnat, we read:
In Asterix and the Chieftain's Shield, the eleventh collection of The Adventures of Asterix, the town of Gergovie is full of "wine and coal" shops, in reference to the bougnats.
Here is a historical photograph of an actual shop for wine, wood, and coal (vins, bois et charbons):

Public domain; from Portail des bibliothèques muncipales spécialisées.