I was thinking of making a CurseWalrein:

@ ?
Brave
252Atk, 129Def, 129SDef
Avalanche
Earthquake
Curse

Therein lies the problem. I was thinking either Hail and make use of Ice Body, or Rest. Which would be better?

As for items, I'm assuming it'd be Icy Rock for Hail, and Chesto Berry for Rest? Or would Leftovers be a better option over both? (Thoguh they are very time consuming to get)

You can actually make use of both by using a Hail team...have someone use Hail, prefably Froslass cos it can Destiny Bond the foe and make it safe for Walrein to switch out. I like the Special Build better however cos Walrein is slow and if you're up against someone with a Super Effective attack Walrein would probably get taken out the turn after it used Curse. This is a build that fits in nicely with a Hail team:

Abiltiy: Ice Body
Item: Leftovers
Nature: Modest
EVs: 252 in Sp. Atk and Hp
Moves:
~Blizzard/Surf
~Stockpile
~Spit Up
~Yawn

Or

~Blizzard
~Surf
~Signal Beam
~Rest + Chesto Berry Combo

I was going for EQ more for the type coverage- nothing except Levitating Bronzong resists Ground and Ice, to my knowledge, while something like Slowbro could probably wall it if Waterfall was used.

or you can add Crunch for better type coverage, Yawn to force someone to switch out and add a leftovers to him...you'll be just as bulky as a swampert and just as threatening with yawn....