As an avid Floatzel user, I can assure you, anything that can survive an attack, will probobly OHKO back with the attacking stats in NU.
Poliwrath, as mentioned, is a great counter to Floatzel. Gastrodon and Quagsire are also great counters, although, the latter more than the former.
Amphoros is capable of takeing a hit, and then OHKO'ing back.
Most NU Grass-types beat Floatzel. Most Floatzel are physical, and even fewer of the mixed/special ones run Ice Beam. Even Cherrim would probobly beat Floatzel.
Noteable Scarfers can defeat Floatzel, as who would run a Scarf on a Base 115, the fastest thing in the teir? Magmortar Thunderbolts Floatzel to death, Primape can Close Combat it. However, if Floatzel is being ran in a Rain Team, Scarfers have no hope, as NOTHING outruns Floatzel in the rain... unless you're running a Scarfed Swift Swimmer. 0_o
Medicham's priority moves also prove useful. Skuntank is a good stop to Aqua-Jet lacking sets.
Porygon2, with it's defences that hold out even in OU, and Thunderbolt, destroys Floatzel. Lacking that, Thunder Wave would do so... as would Tri Attack.
Dusclops is also a decent counter, although, it dislikes Crunch. It will be KO'ed by Floatzel if it's Crunched on the switch-in, then Crunched again on Will-O. Regardless of it hitting, the Third Crunch will KO. SlowKing is a even more shaky counter, also due to it's Crunch weakness, but it lacks Will-O-Wisp, although Slack Off helps greatly.
Faceing down Floatzel in the Rain, however, is not a good idea. As mentioned before, you have NO HOPE of outspeeding a Floatzel in the Rain. WaterFall also has Double STAB, which makes most of the aformentioned counters...not counters. Things get even more hairy if it's packing Bulk Up. If Floatzel's in the rain, and Bulks Up on a switch (Expects a Quagsire, or Poliwrath, for example), things will be VERY nasty, as +1 Crunches/Brick Breaks/Insert Coverage Move Here will damage even these guys... while Floatzel might survive, due to increased defence.
With Rain Support, a Floatzel set like this:
Floatzel @ Life Orb
252 Attack, 0 Speed [NOT NEEDED], 252 HP, 4 DEF [EV's may need tweaking]
Adamant Nature
WaterFall
Bulk Up
Brick Break
Crunch
Very few things can stand in it's way. Switching to a counter risks Bulk Up. Nothing's gonna outspeed it, even with 0 Speed. Your best bet is to somehow stall it out of the rain, when it slows down, becomes vunerable to Scarfers, and Waterfall weakens.