Another 20 IAS will get you from 5/5/5/5/10 to 5/5/5/5/9 (meh) and from 8 to 7 frame Zeal under Decrep. I'd definitely use Eth runes while you're leveling, after that 2 good facets is maybe something you can look at. If you can put Infinity on your merc then you'll never need to worry about AR (this might not be an option, just putting it out there).
How viable is this weapon in hell? I'm doing solo baalruns in multiplayer games in nightmare and he's not killing stuff as fast as I'd expected him to.
I really don't want to do it but I might have to equip him with Grief... which kind of defeats the purpose of having a cold oriented paladin since Grief is all about physical damage.
Viable, certainly, but this char is safe rather than fast.
If you don't want to increase your physical damage with Grief/Oath then there are a couple of things to try. Infinity (this is a game-changer) and Nightwing's are expensive but will help greatly. The resists and speed of a Silence PB would mean you could drop Treachery for an Ormus robe (not that great imo), Guardian Angel (I like this idea) or something else with +skills. Or you could keep the Treachery to reach 4 frame Zeal. The 80%+ CB on your setup is good, but if you stick with Redeemer then I'd say 50% CB is fine and a Shako's boost to cold damage might be better. Voice of Reason's -24% To Enemy Cold Resistance and ctc FO is something fun to look at, though since it has pretty much no phys damage you'd want another weap on switch to pair with it. If you play around with other stuff and can work 4 FPA Zeal (PB + 72IAS) into your setup then that'd be great - it's the very first thing I'd aim to get on a Frost/Tesla-din.