Magnezone is the textbook definition of a counter to Skarmory. It traps Skarmory with Magnet Pull, uses STAB Electric-type attacks to OHKO Skarmory, and resists every move in Skarmory's movepool except the unusable Rock Smash. The only chance Skarmory has against Magnezone is Whirlwinding if Sturdy is active or if it uses Shed Shell. Wobbuffet traps Skarmory too but it isn't a big fan of Taunt, although it can Encore Spikes and Tickle Skarmory to death. After 6 Tickles, Skarmory takes 75.4% – 88.9% if it tries switching out from Choice Band Tyranitar's Pursuit. Specially defensive variants of Skarmory might as well kiss their tin asses goodbye.
Zapdos is immune to Spikes, packs STAB Thunderbolt, can heal itself with Roost, and even counter-phaze if necessary with Roar. All of the Rotom formes have Will-O-Wisp and STAB Thunderbolt going against Skarmory while not taking passive damage from Spikes thanks to Levitate. Politoed changes the weather and attacks with powerful neutral Water-type attacks. Fire-types hate entry hazards in general but they counter Skarmory very well. Heatran hates Spikes, but it can shut down the process with Taunt and singe the metal birdie with STAB Fire Blast. Ninetales doesn't get Taunt but will scare it away just as quickly, and can spread burns with Will-O-Wisp.
Another way to deal with Skarmory is to just get rid of its entry hazards. Starmie can use Rapid Spin to blow away Skarmory's entry hazards, Recover to shrug off Brave Birds, and threatens with Thunderbolt or its Water-type move of choice. Forretress can exploit Skarmory to lay hazards of its own, and it can also use Rapid Spin. Tentacruel does the same thing. Espeon and Xatu may not like taking Brave Birds but they can reflect Spikes back with their Magic Bounce ability.
Since Skarmory is a defensive Pokemon, its hard to directly counter it because it will only come out of the nest when it knows its safe. This makes the concept of luring vital to getting through Skarmory. For example, a stat-booster like Gyarados and Gliscor can use Taunt to beat Skarmory when they would otherwise be walled. Scizor can use Swords Dance and Superpower on an unsuspecting Skarmory. Jirachi can use Thunderbolt in a similar fashion. Pokemon like Tyranitar, Dragonite and Salamence can use Fire Blast to surprise it. Generally, you want to attack its weaker Special Defense with an Electric- or Fire-type move.