Pretty solid advice. Correct me if I'm wrong, though, but I don't think Sheddy can learn Swords Dance, at least according to Serebii's dex.Hm...I think that Heatran would be the best partner. Maybe with a ChoiceScarf and 196 Speed Ev's to outspeed Aerodactyl (201 with Scarf). The last partner should be something bulky too. Maybe Gyarados or something as last filler.
But maybe a other version could be a ShellSmash Batonpass strategy with Smeargle.
As moves I would use SwordDance, X-Scissor, Dig/SunnyDay, SuckerPunch/ShadowSneak
So far I got these ideas:
Gliscor(baton passer) / Sheddy / Heatran (maybe scarfed?)
Gliscor can pass SD and take down Tyranitar with ease. Maybe SD/BT/EQ/Aqua Tail so he can handle Hippowdon, but missing out on Stone Edge may not be ideal
Smeargle / Sheddy / Heatran
Same thing, but with a passer that trades power for Spore and other tricks.
I like the idea of Heatran as a partner to take Fire moves and manhandle the Ice Workers, who commonly carry hail.