I would use Starmie because he can use recover and bolt-beam.
Starmie's Psychic typing gives it a dark, ghost, and bug weakness, in addition to the electric and grass weakness it gets from the Water typing. I'll say it forever: Starmie has too many weaknesses and not enough bulk to care about Recover.
As a spinner, you should generally focus on defensive and team support moves, rather than offense:
Starmie: Gets Natural Cure so it can absorb status. STAB on Surf and Psychic. Screens and boltbeam access. Confuse Ray, Thunder Wave, and Toxic are also available, as well as Trick (though on a Rapid Spin set, there usually isn't room for that). Weak against ghosts, a common switch in to Spinners.
Tentacruel: Pretty good bulk, but it does have a Ground weakness. Gets access to Knock Off, and can absorb Toxic Spikes.
Donphan: Good physical defense, kind of average special. If you heavily invest in defensive stats, it's attacking stats will be fairly pitiful. Gets Knock Off and Rock Tomb (cuts speed by one stage), as well as Toxic.
Claydol: Resists Stealth Rock and has the Levitate ability, so it won't be hurt by Spikes/Toxic Spikes at all. It's defensive stats (Actually, all stats) are fairly average, so it can't take too many hits or do too much damage. Weak to ghosts, a common switch in to Rapid Spinners.
These 4 are the only ones I ever consider using. I usually opt for either Donphan or Tentacruel.