You can find Heracross by headbutting mountain trees (I think), meaning most trees aside from those between Azalea and Ecruteak. I know that the trees east of Ecruteak work... The Heracross trees can drop Spearows and stuff rather than being the ones with the Weedles/Caterpies.
Heracross sets:
Megahorn/Earthquake/Rest/Sleep Talk
Megahorn/Earthquake/Endure/Reversal (poor 'set without Agility BPs)
Megahorn/Earthquake/Rest/Curse
Megahorn/Earthquake/Curse/Counter
Megahorn/Earthquake/Rest/Couter
Megahorn/Curse/Rest/Sleep Talk
(Chris will slap me for this, but regardless of what he says, it works) Megahorn/Rest/Sleep Talk
And so on.