In the end you have to make th choice. Scarf-Mence sits one a rather uncomfortable speed tier with Scarf-Terrakion running rampant but your team can handle him with Lucario and Scizor as backup. When Scarf-Terrakion kills something with Stone Edge, Lucario can get a free SD on it, assuming you run Bullet Punch instead of Ice Punch in the case it comes back. Another reasonable substitute is Alakazam with Psyshock, who is also conveniently faster than Starmie and the ponies. You appear not to consider Keldeo and Terrakion for this job, so we will just leave it that way. Practically every Heatran can run Stealth Rocks, even the offensive Air Balloon one. In that case you just have to watch out for some Landoruses who are ballsy enough trying to break your Balloon, so you need to play a mind game. Does he switch or not? Do I put up SR or kill it? Anyway, I have found Heatran a bit underperforming in non-weather teams because of the abundance of rain in this metagame. Other good choices are special attacker Landorus with SR in general, or Landorus-T with SR when you need a counter to Terrakion. Deoxys-D takes the cake, though.