I would say Heliolisk, since it is the main Pokemon of Clemont, whom you can't challenge until you obtain at least four gym badges, making him the fifth, but it doesn't match all the clues.
My second guess is Poliwrath, as it is a Fighting-type, evolves from Poliwhirl (which can also evolve into Politoed), as is the main Pokemon of Chuck, who can be considered the fifth Gym Leader in Gold/Silver and the remakes...
Anyway, here's my riddle.
From Abomasnow to Krokorok,
I am the Pokemon in the middle.
Final stage Starter, Pure Grass Type
It;s a tough, aromatic riddle.