
No one can touch this bugger (except fire, dark, ghost, rock, and flying attacks; poison(status); burn; stealth rock; spikes; toxic spikes; sandstorm; and hail)
Well, let's ignore those darn parentheses for right now.
What cannot harm Shedinja: water, grass, normal, electric, poison, ground, steel, ice, bug, dragon, psychic, and fighting attacks.
OK, now to address that big list of exceptions: STEALTH ROCK
With stealth rock being the most common move in Gen IV, it seems that shedinja can't get a lot of play time. Well, late-game this might be true, but as a lead, it doesn't have to worry about this.

Shedinja @ Focus Sash
Adamant Nature
Wonder Guard
252 Attack, 252 Speed EVs
-Will-o-Wisp
-Swords Dance
-X-Scissor
-Shadow Sneak
As a lead, Shedinja can have some fun. It can ruin physical bulky leads with will-o-wisp, while boosting its attack against something that can't threaten it. X-scissor is its main attack, while shadow sneak deals with anything that held on with a focus sash. (this notably forces Azelf to break Shedinja's sash or lay SR) Its own focus sash allow it survive one possible death.

Forretress @ Leftovers
Relaxed Nature
Sturdy
252 HP, 112 Attack, 144 Defense EVs
0 Speed IV
-Rapid Spin
-Stealth Rock
-Earthquake
-Payback
Since using Shedinja is never a lost cause, it needs a way to have a clear path back to the fight. Forretress can clear the field with rapid spin and can also give the opponent problems when Shedinja is shifting their team around with stealth rock. Earthquake and Payback allow for moderate damage when necessary.
Now onto Shedinja's 2nd biggest worry, status:
When it comes to sleep, I will sacrifice Shedinja because it is the highest-maintenance pokemon on my team.
Burn is an auto-kill for Shedinja, so it needs a cure:

Heatran @ Choice Scarf
Naive Nature
Flash Fire
252 Speed, 252 Special Attack, 4 Special Defense
-Explosion
-Dark Pulse
-Earth Power
-Flamethrower
Heatran loves taking a will-o-wisp, so it makes Shedinja's life much easier while also taking care of Shedinja's blaring fire weakness, and, to an extent, lessening its dark, ghost, and flying weaknesses. It also functions as a general revenge-killer and can kill one last threat with explosion, while the other three moves provide good coverage.
Paralysis just isn't fun in general, and with an average speed like Shedinja, it does no good. Thankfully, there is an answer:

Electivire @ Expert Belt (Don't tase me, bro!)
Mild Nature
Motor Drive
36 Attack, 220 Special Attack, 252 Speed
-Thunderbolt
-Cross Chop
-Hidden Power Ice
-Flamethrower
Electivire is a threat to begin with, but add a speed boost and it becomes a potent threat. It is mixed to prevent itself from being walled by most things. HP Ice and Thunderbolt create the infamous bolt-beam combo, while cross chop and flamethrower usually hit super-effectively against anything neutral to bolt-beam.
The final true inflict-able status, poison. True, Forretress and Heatran are immune to poison, but I would like to avoid potentially losing my spinner by blocking a poison assassination on Shedinja and to cover more of Shedinja's weaknesses by adding another steel:

Lucario @ Leftovers
Naive Nature
Steadfast
56 Attack, 252 Speed, 200 Special Attack
-Aura Sphere
-ExtremeSpeed
-Dragon Pulse
-Crunch
Lucario covers Shedinja's rock, dark, and ghost weaknesses, with 4x, 4x, and 2x resistances respectively. Aura Sphere provides consistent damage, while extremespeed deals with trick-roomers or other priority users. Dragon Pulse and Crunch provide good coverage and complement aura sphere.
Now, I now that many of you noticed 3 heavy weaknesses to ground. (I noticed it, too) So the final pokemon covers this weakness, and provides part of the offensive core for this team:

Gyarados @ Life Orb
Jolly Nature
Intimidate
252 Attack, 4 Defense, 252 Speed
-Dragon Dance
-Waterfall
-Earthquake
-Stone Edge
Gyarados complements the rest of the team nicely, and provides perfect symmetry with Electivire. This team causes lots of switches, so Gyarados can easily get up a dragon dance and then proceeds to wreak havoc. Earthquake and Stone Edge provide great coverage by themselves, so this set provides excellent physical coverage.
Overview:
Shedinja is portrayed as a huge gimmick in OU, but this becomes a surprise factor as a lead and can force the opponent to reveal their team long before they want to, which allows my offensive core of Gyarados, Electivire, and Lucario to view their opponents' counter ahead of time. Forretress allows Shedinja to keep coming back, and Heatran avenges any death (especially Shedinja's) on my team.
All suggestions welcome,
Server_Crash