Landorus-Therian
After an Intimidate, Heracross doesn't hit nearly as hard as it usually does. Landorus resist Heracross's STAB and takes neutral damage from its standard coverage moves (Bullet Seed and Rock Blast). Landorus doesn't really hit Heracross very hard though, it's more of a defensive counter. Landorus is very easy to incorporate into a team due the the vast amount of new Mega Pokemon it beats easily, and because it has a very good chance to OHKO Greninja (a huge threat) after rocks.
Fast Flying types
Heracross dies to Flying moves, and it's not very hard to outspeed either. It's open to many Flying attacks, such as Return from Mega Pinsir and Brave Bird from Talonflame.
Gliscor
Heracross cannot touch Gliscor at all. It takes minimal damage from everything Heracross can throw at it, and can toxic stall it to death or force it to switch.
Fairies
They resist Mega Heracross's STAB attacks and can take neutral hits from coverage moves. They can then respond with a strong Fairy attack. Physically defensive Clefable is one that works particularly well. Mega Diancie is also a good way to remove Heracross if you want a more offensive Pokemon.
Pokemon that can revenge kill it
If Heracross uses Close Combat to beat a Pokemon, take advantage of the defence drops and smack it with a super effective move. Basically anything with a decent Speed stat is capable of this; remember that Heracross is slow.
