The pokémon you can find by Headbutting trees depends on where you are. You'll find different species depending on whether you're in a more lowlands forested region or a more mountainous region (and Ilex is a region unto itself.)
To find Heracross, look in the mountainous regions. Route 42 is a good spot, I think. It's gonna be very rare, like maybe on the order of 1%...but 1% beats the pants off 0%, which is what you're looking at if you try somewhere like Route 36.