I consider Fletchling's case a case of
hysterical strength, aka the display of incredible and seemingly impossible feats under severe stress and the effect of adrenaline, and this same principle has been applied several times to various other situations. It isn't anything new to the anime, so I wonder why it is suddenly such a big deal now. Also, the bird studied its opponent before the battle and was determined to prove it wrong, so that further fuelled its capacities. If you are determined to do something, you can bet that you'll put everything in stake and do better than usual. That's what happened with the little robin.
Besides, remember that Fletchling was a wild Pokémon before its capture, so it must have had several battles during its life in order to survive in the wild. It's not like it has been just hatched like Scraggy and as such doesn't have strength or experience. After all, Ash wanted to catch it especially for its power, which is the same reason why he caught Palpitoad. It's just that said power needs to be polished by the Trainer and used to its maximum potential. In fact, isn't that the job of a Pokémon Trainer? To bring out the full power of a Pokémon and to make it stronger?
But let's compare Fletchling with the previous little birds, shall we?
Taillow
Battles: unfinished battle against Nicholai, lost to Anthony's Pelipper, lost to Brawly's Machop (in a single hit!), lost to Drew's Roselia
Evolution: PokéRinger (AG080), evolved through sheer determination, which managed to make it resist Electric-type attacks and defy a powerful storm, and learned
Wing Attack upon evolution
Starly
Battles: lost to Paul's Starly
Evolution: against Team Rocket (DP013) while wanting to help other Flying-type Pokémon, and mastered
Aerial Ace upon evolution
Pidove
Battles: lost to Trip's Frillish
Evolution: while warding off the Venipede (BW022)
Fletchling
Battles: won against Viola's Surskit, lost to Viola's Vivillon (twice), lost to Grant's Tyrunt
Evolution: Sky Battle (XY035), evolved through sheer determination, where it used its little dimensions to dodge its opponent's attacks and to endure a Fire Blast, and learned
Flame Charge upon evolution
By looking at these, Fletchling is one of the birds who deserved to evolve the most, if we consider the loss/win ratio and take the number of episodes spent under Ash's command as a measure of time. Starly and Pidove were way quicker and did way less. That's of course if we consider only the birds, but there are worse cases of "undeserved evolutions" (*cough*Sewaddle and Roggenrola*cough*).
So no. I don't consider Fletchling's evolution and win DEM, especially not after taking in account that the bird studied its opponent beforehand (so it didn't resort to luck, for once), managed to hold its own for a while and won thanks to various speed-boosting Flame Charges, which made it way harder to hit. And at least Talonflame didn't fall to a single attack after the bird evolved, contrary to Skyla's Swanna (which, may I remind you, was the Gym Leader's ace) who was taken down by a single Aerial Ace, so it isn't like it has been overly humiliated as a species.
Anyway, about the future Gym battle... meh, I already voiced my opinion on the matter, so I'm not gonna bother saying it again and again. I just want this to be over already, so that we can finally move on from this overhyped Lucario.