Murkrow @Evolution Stone
EVs: 232 HP/152 Def/124 SpD
Sassy Nature (+SpD, -Spe)
0 Speed IVs
Mischievous Heart
- Perish Song
- Mean Look
- Protect / Roost
- Substitute
Basically, if you can get both the Perish Song and the Mean Look off, it's a guaranteed kill, because both Protect and Substitute have priority. Roost is also an option over Protect since Murkrow can easily Roost off his weaknesses for a turn, and he has 319/237/249 Defenses with this spread, which is pretty bulky (I got the spread from X-Act's defense EV optimizer), so there's a good chance that he'll last enough time to full off a successful Perish Trap. I used absolute minimum Speed because I saw Lee's post about how he did the same with Erufuun to lessen Gyro Ball damage. That seems pretty useful since it means Nattorei will be in quite a pickle if he comes up against you. Plus you really don't need the Speed unless you're facing other Mischievous Heart users, who most likely aren't investing in Speed either.
Of course, if you're afraid of accidentally trapping stuff like Tyranitar, Confuse Ray is an option over Sub.
The EV spread probably isn't the best since I didn't specialize toward anything, but it seems like an awesome concept, especially against Stall teams.