Physical Walrein lol.
Anyway since Walrein has base 80 attack, obviously you want to maximise that out. It's speed is useless anyway, so we can chuck that out the window, same with SpA since you aren't using it.
Anyway I'd probably run an EV spread of 232HP/ 252 Atk/ 24 Def (with Adamant nature :P)
This is to maximize Walrein's attacking capabilities, as well as giving it the bulk required to take some hits and dish them back.
You could change one of the moves (Zen Heabutt?) for Curse, to buff up Walrein's attack
Anyway in regards to thinking of a new moveset, that's probably the best idea. Walrein is designed for Stalling/Some special attacking in contrary to the physical set you're running right now :P. A more generic type of Walrein would be;
Walrein @ Leftovers
Ability: Ice Body
EVs: 232 HP / 36 Def / 216 SpD / 4 Spe
Bold Nature
~ Substitute
~ Protect
~ Surf
~ Toxic
Obviously this Walrein basically has to function in hail. Stallreeein :D