Rhydon and its Ground / Rock friends are the only true counters to Zapdos, which lacks the traditional Electric weakness and effectively Drill Pecks every other potential Electric counter. It's not easy to switch in due to a very low Special and many weaknesses, but Rhydon will dent whatever switches in against it. The best opportunity comes against something Rhydon fully counters, such as Dodrio or an Electric-type. Its ability to kill an incoming Starmie with some luck can't be ignored. Rhydon is strong late-game at finishing off teams of paralyzed Pokémon. It is usually not paralyzed itself due to its Thunder Wave immunity. With some prediction, Rhydon can switch into Hyper Beams for a free attack and take Explosions without dying.
This set is not very difficult to use. Body Slam paralyzes Starmie and Exeggutor. Rhydon's Earthquake is the strongest physical attack in the game that doesn't have any kind of drawback, and Rock Slide hurts Flying-types for super effective damage.
The trickiest problem is dealing with Starmie. For example, say you predict Starmie will switch in and use Body Slam, and it does switch in and you are lucky and Body Slam paralyzes Starmie. After that, you can 2HKO Starmie, but if it has Surf it will OHKO Rhydon. After this, you ought to use Substitute and hope that Starmie gets fully paralyzed. Maybe it won't, but Rhydon will be able to set up 4 Substitutes before running out of HP and then it will have one more chance of using Earthquake before Starmie finishes it off, meaning it has a 76% chance of getting off 2 Earthquakes against that Starmie (as well as a reasonable chance of finishing it off with a Substitute still intact, should it get fully paralyzed twice).
Do not use Substitute before you have another Pokémon asleep (activating Sleep Clause), because it is too easy for Exeggutor to switch in for free while Rhydon does 25% damage to itself; it can then get put to sleep by a quicker Exeggutor.
Horn Drill is an option if OHKO moves are unbanned, although you'd first need to paralyze your foe in order to use it due to Rhydon's low Speed. Rest and Hyper Beam are usable, but none are especially good options. In general, it's better to just stick with the set mentioned above. Don't bother with Surf, either: as it's only a 2HKO on Golem, Rhydon will lose to it every time anyway.
Checks and Counters
Exeggutor is the safest switch-in. Tangela, Vaporeon, and Sandslash are sure bets, but they're not commonly used. Starmie can also get in on Rhydon, but watch out for paralysis. Venusaur is also a good counter despite its partial Poison typing letting Earthquake do normal damage. Lapras doesn't like Rock Slide, so be careful if you try to switch that in on a Rhydon. Essentially, Water and Grass Pokemon that can take a hit should be able to counter Rhydon, as most STAB Water and Grass attacks normally OHKO it.