Evolve it the minute you get Flamethrower i.e level 50. Use your Fire Stone at this level and the newly evolved Arcanine will also learn Extreme Speed, which is a really nice plus to have. It will take patience no doubt, but some grinding at Victory Road should get you there.
Keep in mind that once you evolve Growlithe, it can no longer learn Flamethrower, which is a shame since its the best Fire type move.
Hope I helped!