I remember having a Politoed on my first Playthrough of Soulsilver (I named him "Ribbit," because I'm that frikken' origninal)... Anyway, this is a fairly mediocre moveset for Politoed, except for Ice Beam. Hyper Voice is debatable, but I won't go into the controversy.
The quesiton is whether you want a Special-based, or Physical-based Politoed. Believe it or not, Politoed can utilize both extremely well (Just as a warning, NEVER try to mix Special and Physical attacks on Politoed. For some odd reason, everything just begins to clash).
I'll make this quick, and give a small overview of both routes:
Hypnosis (Put your opponent to sleep.)
Belly Drum (Use this right after Hypnosis for the Attack Boost. Make sure you have Leftovers attached!)
Brick Break/Earthquake/Bounce (Yes, the little amphibian can learn all of these attacks. Brick Break to deal with Steels. Earthquake to hit Steels, Rock, Electric. FInally, use Bounce to deal with Pesky Flying and Grass-types.)
Waterfall (Your physical STAB, with a chance of flinching.)
Hypnosis (Put the opponent to sleep.)
Surf (Your Special STAB with incredible power!)
Ice Beam (Use that to deal with pesky Grass, Ground, Flying, and Dragon-types. The chance of Freezing is pretty overlooked, seeing as your focus is to inflict sleep on the opponent.)
Focus Blast/Mud Bomb/Psychic (Focus Blast is your equivalent to Brick Break, except stronger. Mud Bomb is your Special alternative to earthquake. Psychic is used to hit Tentacruel, Muk, and other Poison-type Special Walls that try to counter you.)
These are my best recommendations for Politoed. It's got a great movepool, but the tough part is deciding which ones to use. Like I said, it can sweep Physically AND specially, but because the physical route needs Belly Drum support, there's no room to add diversity in Special moves. Like I mentioned beofre: mixing the two causes clashing.
I hope I helped!
EDIT: OOPS, you already picked a best answer for this question. My bad. xD