The leaf Stone can be found before even the 3rd badge theres a trainer in route 34 called picknicker gina who has 2 hoppips and a bulbasaur. Get her number if you walk enough in a route not being route 34 she calls you go to route 34 and she gives you a ......Leaf Stone!!
Source: Knowledge
I had a lot of Vileplume and Victreebel besides me in Pokemon G/S/C I always get a leaf stone that way