I don't think Houndoom is too slow to use Nasty Plot. If you run Hasty (+Spe / -Def) with 204 Spe EVs, you outspeed all +Spe-natured base-120s (since this is an in-game team and not an s-crmt).
So I'd suggest:
Houndoom @ Leftovers / Life Orb / Wise Glasses
248 SpA / 204 Spe / 56 HP
~ Nasty Plot
~ Flamethrower / Fire Blast
~ Dark Pulse
~ Hidden Power [Grass]
Pretty much the same as what Aurath8 posted except with different EVs, nature and running Nasty Plot > Sucker Punch. Also, the given EVs let you hit a Lefties number in terms of HP ((HP - 1) is divisible by 16).