I'll just respond to a few things I read (I'll the specific quotes afterwards) and then give my take.
Alain's Charizard didn't really go "toe to toe" with Steven's Metagross. It just didn't get immediately KO'd by it - Charizard was resistant to both the moves it was hit by (Flash Cannon and Meteor Mash, specifically). Given that Blast Burn failed to do any visible damage to Metagross it's likely Charizard would've lost before too long if the battle wasn't interrupted.
I'm fairly certain Paul could defeat the rest of Alain's team, particularly given Ash's Kalos team could, and Paul regularly combines more experienced Pokemon with less experienced Pokemon, and he could just bring a stronger combination of Pokemon than he did in the Sinnoh League.
Torterra alone could probably KO both Tyranitar and Metagross. He's immune to the Sandstorm, resists Stone Edge and could probably use his own moves to deflect or overpower Dark Pulse and Crunch, plus deal Super-Effective damage with his Ground and Grass-type moves. We even saw him take a super-effective Fire Fang from Gliscor without too much trouble, so a neutral Crunch should be fine. While Pikachu without its early-region limiters is really strong, the fact of the matter is that he resisted Metal Claw and Meteor Mash. Torterra is probably even bulkier than region's-end Pikachu and resists Rock Slide, whilst also having Super-Effective Ground-type moves he can use. His battle style also assumes that his opponents are always faster than him, so adding Agility to the mix wouldn't be anything he hasn't dealt with before.
Ursaring or Electivire could KO Bisharp and/or Weavile - both have access to Fighting-type moves and either grow stronger from or are immune to Thunder Wave. Electivire also resists any Steel-type moves Bisharp might have. And Weavile's evasive tactics wouldn't do much when Electivire can use Thunder to send rocks flying from the ground. If Paul were battling Ash in place of Alain he could've also just electrified the water in the Rock battlefield they fought on first.
Honchkrow probably could've tied with Unfezant as well - we've already seen it make use of Super Luck, which Unfezant might have as well. And Honchkrow's Sky Attack is probably comparable in power to Unfezant's, as well as Talonflame's Sky Attack.
The obvious issue is Charizard. Alain generally doesn't bother Mega Evolving Charizard unless his opponent has access to a comparable transformation (in other words, he tends to underestimate his opponents - we even saw this when he didn't bother Mega Evolving Charizard until he saw Remo's Garchomp knew Draco Meteor.)
Base Charizard was able to KO at least Rhyperior on his own, but was also able to be outsped and dropped to one knee by (an extremely weakened and tired) Pikachu. And Paul's already been seen dealing with opponents who assume they're more powerful than him with the battle against Cynthia, where he baited Giga Impact. So I imagine he'd make use of the fact that Alain hasn't seen a Mega Evolution from him to lure Charizard into fighting without Mega Evolving immediately. Electivire has managed to withstand Blazefernape's Flamethrower using Thunder, and stay standing after clashing with its Flare Blitz. I'm fairly certain the firepower of Alain's base Charizard isn't as great as Blazefernape's, so Electivire could likely get a Thunder in before fainting. And he locks Charizard out of Thunderpunch (or takes it and speeds up).
As aforementioned, Destiny Bond Froslass would be a very suitable tactic for Paul, though obviously it's a bit of conjecture since he hasn't taught her that move, to our knowledge. But if the writer were to write this battle with Paul knowing about Mega Charizard X, it'd be odd for them not to toss that idea around in the writer's room. Drapion did fall to Gliscor's Fire Fang, so odds are he couldn't take Charizard's for very long. But Charizard also tends to stand on the ground a lot prior to launching Thunder Punch or Dragon Claw, so Drapion's Toxic Spikes could be useful in keeping him away. Pin Missile would probably also hit, since Gliscor was unable to dodge it even after specifically training in precision flight, though it wouldn't do much damage. Magmortar could also take some hits and defend/attack with Rock Tomb. Given he took Water-type moves from Buizel he could probably take Flamethrower easily.
TD;DR this match would likely be very close. If Paul can get in enough damage before Charizard Mega Evolves, the remainder of his team might be able to tough it out and defeat Mega Charizard X through attrition (and as has already been said, Paul already managed to bring Cynthia's Garchomp to its knees using that tactic. If the writers wrote Blast Burn as they had other recharge moves back in D/P, then Paul could likely use the tactic even more effectively against Alain's Charizard).
The team and likely battle matchups could be as follows:
1) Torterra VS Tyranitar - Torterra wins and is recalled.
2) Ursaring/Electivire VS Weavile - Ursaring/Electivire wins, is recalled for whichever of the two didn't battle.
3) Ursaring/Electivire VS Bisharp - Ursaring/Electivire wins, is recalled.
4) Honckrow VS Unfezant - A draw.
5) Torterra VS Metagross - Torterra wins and is recalled.
6a) Drapion VS Charizard - Lays Toxic Spikes, deals some damage, Charizard wins.
6b) Ursaring VS Charizard - Ursaring might deal some damage, but most certainly loses.
6c) Electivire VS Charizard - Electivire uses Protect to wait for an opening, lands Thunder Punch and Thunder before fainting. Charizard probably Mega Evolves here after sustaining more serious damage. Is also poisoned, still.
6d) Magmortar VS Charizard - Magmortar could probably fake Charizard out by hiding behind Rock Tomb, letting Charizard smash through, avoid the hit, and then hit Charizard with Rock Tomb. Given that getting close to use Dragon Claw or Thunder Punch is dangerous due to Rock Tomb, and Flamethrower could be held off with Magmortar's own Flamethrower, Charizard could probably just Blast Burn here like he did with Mega Houndoom. Magmortar faints.
6e) Torterra VS Charizard - Both are exhausted, but Charizard is also Poisoned. If they write Blast Burn with recharging, Torterra immediately KOs it with Stone Edge, Earthquake, etc. Without recharge, Charizard either wins, faints to the Poison before it can land a hit, or Torterra somehow manages to land one more hit before fainting and force a draw if he faints right after.