Based on a Lavos Skeleton and fleshed out by me
Heracross has a decent SpDef stat and a really high Attack, which lets it take quite a few hits on the Special side and fire back hard on the Physical side. Its Bug typing is both a blessing and a curse, meaning it can switch into the very common Earthquake easily (effectively checking Nidoking and Steelix, for example, since they rarely pack any Fire-type moves) but also leaves his only prominent STAB move resisted by very common types such as Flying and Steel.
Set 1: SleepTalk
Move 1: Rest
Move 2: Sleep Talk
Move 3: Megahorn
Move 4: Curse / Seismic Toss
Heracross has quite the shallow movepool and a decent combination of bulk and typing, which makes RestTalking the perfect strategy for it. Megahorn is the 120 Base Power STAB nuke, which heavily dents anything that doesn't resist it. Curse and Seismic Toss round up the set providing respectively late game sweeping power and a better way to hit Skarmory so another teamate (like Marowak or DrumLax) has an easier time taking it down.
Unfortunately, most things that do resist the main move are quite common and shut Heracross down quite easily, like Zapdos and (especially) Skarmory, so getting rid of its common checks is crucial for Heracross to shine. Even Seismic Toss does 30% to Skarmory and even less to Zapdos, so even if you get them on the switch, it's usually best to just switch Heracross out.
Earthquake provides really good coverage, since it hits things like Gengar, Nidoking (who otherwise might stay in to chip Heracross) and Raikou (practically securing the 2HKO that Megahorn almost always fails to get) super effectively, but it does nothing to combat Hera’s main problem of Zapdos and Skarmory being unbreakable, so the main set is usually better.
You can opt to have a Curse+3 attacks (Megahorn, Earthquake and Hidden Power Rock) set if you want to exchange staying power for offensive pressure. This set works like a poor man's Curse Machamp, with better special bulk and key resistances, but it has a worse STAB move and is still hard walled by Skarmory, like the main set.
An Endure+Reversal set is marginally viable, but Heracross isn’t fast enough for it to be consistent, not to mention it’s only a one-time use if Spikes are in play.
[Checks and Counters]
Skarmory is the best defensive check, while Zapdos is the best offensive one, but Charizard and Dragonite, though far less prominent, are safe switch-ins too for almost all Heracross, bar less viable Hidden Power Rock sets. Keep in mind that Dragonite must have super effective moves or Heracross might chip it down. Steelix can’t do much besides trade with Explosion or Roar it out, but it’s hard to break and takes 5 Seismic Tosses to KO (Earthquake does roughly the same damage, but far less if Steelix already has a Curse under its belt, which is usually does). Miltank can switch in safely enough and Growl your damage and/or curse pp away while healing up with Milk Drink, but it can't really damage Heracross. Gengar is immune to Seismic Toss, takes negligible damage from Megahorn and can threaten Explosion or Destiny Bond, but must watch out for Earthquake if it doesn't want to trade and Curse sets can mitigate the danger of Explosion while helping with DBond mindgames. Do note that unless Gengar is carrying the rare Fire Punch, it cannot force Heracross out without threatening to also faint. Heracross can check itself, but it's not recommended unless you're ok with starting a pp war with your opponent or you're packing Curse and they're not.
EDIT: Added the suggested OO set and reworded the CC section to note that dnite must be the defensive set and to show that Skarmory is clearly a better counter than Zapdos. Added Miltank to the CC and noted that Gengar must watch out for curse sets and can't force Hera out too.
EDIT2: changed the part about defensive Dragonite, added that it must have the correct moves. Reworded how Zapdos and Skarm check Hera. Also corrected minor english mistakes :p