Here are a few suggestions.
Weezing-He resists fighting, is slow enough for Paback not to have any serious damage, has lots of physical bulk, and has plenty of special moves/disrupting moves to wear away at Conkeldurr. He's even got the move Clear Smog to deal with Bulk up sets.
Skarmory-This guy is a bit harder, but he's neutral to fighting, resists dark, and gets STAB from flying, so you can run a few sets like that.
Jirachi/Metagross-These guys have tons of defense, are neutral to dark and fighting, and can take him out pretty badly with psychic moves. You can also use trick with any pokemon that learns it and give him something like choice specs.
Salamence-Salamence comes in with Intimidate to cut his attack and Fighting resistance while breaking him with moves like Draco Meteor. Don't give me crap because his attack is higher, since 110 base special attack is still very good.
If you know it doesn't have bulk up, you could counter toxic Orb abusers with a speed booster by just stalling things out with Sub/Protect and let the damage take him down. Priority moves are very useful in this case. For instance, when I use Sub/protect sharpedo against him. I just stall things out and let the damage add up. Then you can finish him with a priority move.
In short, Almost anything moderately fast with high Special Attack and neutrality to Fighting, or can utilize some STAB flying can revenge kill it. Just make sure it has some bulk.