Tokheim:
I like re-rolls for armor saves,
I also really LIKE high strength attacks, especially if your Overlord is going to be in a unit of plain jane vanilla HW/SH warriors. He probably needs a magic weapon for the ST, in case he could possibly hit first or has to hit something that requires magic to wound it. Toughness 5 is our friend, awesome stuff, but there is so much out here that can wound him even still.
I like your last option listed above most of all.
One thing I liked from the old 8th edition rules was the shield where you discounted the first hit on a 2+. Don’t we have something similar, is it the “new” Lucky Shield? Anything to keep him alive dishing out attacks!