Heracross? I'm almost positive that celebi wouldn't switch into nor stay in against a heracross of any kind. Megahorn probably does chunks to amoongus so would probably only come in on a close combat...Heracross
Celebi w/ Psychic/HP-Fire/U-Turn.
Starmie w/ Psychic/Signal Beam/HPFire
Celebi is cool, but HP fire is kind of a standard these days and it isn't doing a whole lot to Amoongus.
Starmie would be perfect. Psyshock / Signal Beam would be awesome lures but for some dumb reason Starmie doesn't learn Signal Beam :( Unless it got it as a move tutor?
And get trapped? All three of these are commonly found on sandstorm teams. There's a reason why you never see choiced Psychic types in OU very often, if at all.Instead of luring them, you probably ought to just trap them with Choice Specs Gothitelle. It learns Psyshock and Signal Beam, and can use HP fire for Ferrothorn.