Please don't give me the answer Nacrene City.
So I guess you already got the Charcaol in Nacrene City? If you didn't, it's here:
>From a girl in the west-most house if the player answers "Tepig"
The Other one is on Route 16.
>Northeast, behind the fence (requires Strength)