Here are a few things that seem like counters that haven't really been mentioned at all in the thread yet, but are mostly viable enough that they can exist on their own without the express purpose of messing this set up.
In general things that can deal enough damage to break a sub and have priority moves can counter this set to some degree (this was mentioned earlier with the case of a slow, bullet punching Metagross but there are other users of this type of moveset as well).
The selfish SD scizor mentioned in the second post of its analysis thread works to a certain extent; it is slower than Skarmory and therefore slower than this set, can easily break a sub with brick break, either SD or brick break during the first protect (an SD stands a good chance of getting roared out if you realize what set it is, but it also makes it that much more painful if you play it safe and protect), then quick attack before you can sub again. A life orbed quick attack before SD only does about 18-21%, but an SD boosted quick attack does 35-42% and an unboosted brick break does 44-52%, so if you mispredict during the "protect" stage you could be hurt pretty badly. Unfortunately this Scizor runs life orb which means it can probably only afford to do this a few times before it kills itself. That is potentially enough time to stop this set though if it makes the right choice during the protect turn. (I know that roost Scizor was already mentioned but I figured I'd mention this set too).
Another user of this type of combination is Breloom. The Anti-Starter (Spore/Seed Bomb/Protect/Mach Punch) variety can be EV'ed with no speed, or alternatively 4 speed. The former will always go after walrein, while the latter ties Walrein but is able to guarantee going ahead of Skarmory (which is probably more realistically useful in the general sense and as I'll mention in a minute isn't really so bad anyway in this specific case). Breloom has the nice advantage of being able to heal even in the hail, as well as being immune to Toxic Spikes. However, it has the decided disadvantage of being OHKO'd by Blizzard, so it's really only a counter to the Surfing variety of Walrein. Nonetheless, Mach Punch does a respectable 27-33%. Furthermore, since it ties exactly with Walrein in speed, half the time its Seed Bombs will be going first, and half the time they'll be going last, which means if the Breloom user is feeling lucky they can Seed Bomb instead of Mach Punching when the sub is down and end up doing 54-64%.
Speaking of Breloom, another counter, or set of counters really, are sub-punchers that are faster than Walrein. In general, they can basically do the opposite of what slower priority move users do, which is break your sub with Focus Punch and then hit you with their other attack while you're unprotected. Really, any sub-puncher with reasonable special defense will work alright, but some are better than others:
Sub-punching Weavile and Abomasnow heal off damage in the hail, so they'll be regenerating substitutes eventually as long as Toxic Spikes is spun away. It may not be the most immediately obvious option when building a set for him, but I don't really see any reason why sub-punching weavile wouldn't be viable, especially with his STAB attacks covering most of the types that resist fighting so well. Somehow though I doubt that Abomasnow will see OU play except in hail teams.
If not though, there's always Breloom again. As long as it's carrying Stone Edge and not Spore, it can Focus Punch away subs and then either Stone Edge or Leech Seed once they're down. In this case, it may even be able to counter the Blizzard variety as long as it isn't killed on the switch, because Breloom can sub 5 times in a row even if its subs are killed each time, which would be a real strain on Blizzard's PP. Plus, chances are it will get at least one sub up successfully before the Walrein user knows what set it's running anyway.
Finally, the set that once you look at it seems like it was just MADE to counter this Walrein: the Toxicroak subpunching set. Not only is it immune to toxic spikes, it changes the weather by the very design of the set, and just to add insult to injury it is actually healed by Surf. I know you've already mentioned that rain dance teams mess up your strategy, but the nice thing about this set is that's it's viable in its own right on a non-rain dance team (well... maybe. I haven't actually used it. But it seems like it might be).
By the way, I'm not trying to question the effectiveness of your set here, I'm just hopefully bringing up a few ideas on how to counter it.
Edit: wow I should have previewed this before I posted; I didn't realize how tl;dr it is. Maybe I'll make it look nicer tomorrow.
