I hate those staller Walreins!!! They can Stockpile without taking too much damage! Does anyone know any good Pokemon to counter them?!
Virtually any Taunt user shuts down Walrein completely, as they prevent it from using any of the annoying status moves you mentioned above. In addition, most strong super effective hits (particularly after using setup moves like Swords Dance or Nasty Plot) do a pretty effective job, as well as residual damage from moves like Toxic or Leech Seed.
Here is Walrein's Page on Smogon for further reference. (Note that this is the XY edition, as the Sun and Moon one has not been made yet.)