Conveniently, bulbapedia provides a list of shedinja counters...this. Yes, that is everything that can carry hidden power in some way or another...they may not use it but hey, predict the switch into shedinja, fire off a hidden power [rock, etc] just because it seems like a really cool and popular move, outspeed it the next turn, gg mr cicada shell. (Btw, yes, ditto counters it, too, predict a switch into shedinja, transform, then fire off shadow sneak if it, like most shedinja sets posted thus far, carries it.)

It is also the most easily toxistalled pokemon out there. Heck, it even brings up a new type of stall that ninjask can pull off...weather stall. How? It's simple, just have abomasnow/snover or hippopotas/hippowdon/ttar and wait half a turn. That's how long it should take for weather to kill it. As a matter of fact, anything that has the balls to carry sandstorm or hail with no real use for it weather stalls shedinja. Yes, ninjask gets sandstorm, but with it, it becomes taunt bait, aka useless.

Even having SR/Tspikes/spikes down kills it. Getting it roared/whirlwinded in kills it. This kind of makes air balloon viable, yet...a sub would have to be passed to it. (Having a rapid spinner is a MUST when using shedinja.)

Anyways, with a horrific 40 base speed, it ain't gonna outspeed much anytime soon, especially in the ubers tier. It can effectively force switches and punish whatever switches in with whatever you want. It would have to get out quick b/c, well, it's the ubers tier for one if it's used there, and 2, magmortar runs rampant in NU, as I've heard from a certain mod friend of mine...also if someone choses to use that there.

This seems to be the best set there is for it:

Cicada s-hell
Focus Sash
Wonder Guard
Adamant Nature
252 atk/252 spd/4 wherever, won't matter anyways
~Will-o-Wisp/Toxic
~Swords Dance
~Baton Pass
~Shadow Sneak/X-Scissor
Basically...WoW to punish switch ins that aren't fire type, toxic if you rly fear those or could care less about physical attackers. Swords Dance for any switch in you feel won't die from a single shadow sneak or are just paranoid. Baton pass if you were really in there just to sponge up an attack and make you look pro with the safe double switch or want to pass on a SD. Shadow sneak is for actually doing damage on the 2nd turn, x-scizzor is for the punishing if you manage to survive the 2nd turn.

Overall, shedinja has 2 uses, both of which it would seem to do well with--a switch in punisher, and, probably the best use, something that can guarentee a safe switch.