I think you might find Hawlucha to your liking.
Hawlucha actually gets a lot of support moves, and it's decently fast. It eats up Thunder Waves thanks to Limber, and can be a great teammate.
Hawlucha @ Leftovers
EVs: 252 HP / 252 Spe / 4 Atk
-Drain Punch / Stone Edge / (basically whatever you want here)
Quick Guard protects both of you from Talonflame's Brave Bird, and Tailwind boosts the team's Speed. Mega Heracross has low Speed already, and this can only help. Helping Hand will make Heracross's attacks absolutely nuclear. The last move is your choice.
What ability does it have before Mega Evolving? I suggest Moxie because if you can net a KO...
+1 252 Atk Mega Heracross Helping Hand Bullet Seed (5 hits) vs. 252 HP / 252+ Def Hippowdon: 510-610 (121.4 - 145.2%) -- guaranteed OHKO
EDIT: I actually read all of the question.
Now, Heracross is weak to Flying 4x and Psychic, Fire, and Fairy 2x.
Looking at these weaknesses I believe Tyranitar might be a good partner. Tyranitar is a commonly used Pokemon, so it's quite possible that your Multi Battle teammate has one. Tyranitar resists Flying and Fire, and is immune to Psychic. The Fairy weakness is mildly mitigated as the grand majority of Fairy moves people use are special, and Sandstorm boosts Tyranitar's SpD.
Here's the T-Tar set:
Tyranitar @ Leftovers
Ability: Sand Stream
252 HP / 64 Atk / 160 Def / 16 SpD/ 8 Spe
252+ Atk Choice Band Talonflame Brave Bird vs. 252 HP / 160 Def Tyranitar: 93-111 (23 - 27.4%) -- possible 5HKO after Leftovers recovery
252+ SpA Choice Specs Pixilate Sylveon Hyper Voice vs. 252 HP / 16 SpD Tyranitar in Sand: 368-434 (91 - 107.4%) -- 43.8% chance to OHKO (Hey, at least it's less than half!)
64+ Atk Tyranitar Iron Head vs. 252 HP / 220+ Def Sylveon: 168-198 (42.6 - 50.2%) -- 94.1% chance to 2HKO after Stealth Rock, sandstorm damage, and Leftovers recovery
This is a reliable switch-in to Talonflame, and can beat most variants of Sylveon. The 8 Speed EVs allow it to outspeed standard Specs Sylveon by one point and net the 2HKO with Iron Head.
And finally, the last team member:
Xatu is a useful lead in a Multi Battle, as he gets moves like Reflect, Light Screen, and Tailwind, and he has Magic Bounce, which prevents direct status and bounces back Spikes, opposing Stealth Rocks and Toxic Spikes. Here's a moveset for a lead Xatu:
Xatu @ Light Clay
Ability: Magic Bounce
EVs: 252 HP / 252 Spe / 4 Def (or SpD, doesn't really matter)
Xatu starts off with Reflect and Light Screen, which allow you to tank hits even better. Remember Tyranitar, who got mauled by Specs Sylveon?
252+ SpA Choice Specs Pixilate Sylveon Hyper Voice vs. 252 HP / 16 SpD Tyranitar in Sand through Light Screen: 184-217 (45.5 - 53.7%) -- 2% chance to 2HKO after Leftovers recovery
BAM. You can net a clean 2HKO with Iron Head afterwards. Tailwind, as previously stated, boosts Mega Heracross and Tyranitar's low Speed stats so that they can do their job better.