I don't think he should be invincible even without the Godslayer, I like the idea of a group of heroes working together to bring him down (RPGs FTW!), but he should really be unkillable by normal units, and it should take at least 2 or 3 heroes to wear him down. What I'd like to see is a 2 first strikes, maybe 3, to make most of his combats flawless victories, and a 20% heal after combat to make up for the occasional lucky C5 immortal or whatever that lands a couple hits on him. Blitz would be nice but frankly attacking, what, 4 times? every turn would just be begging your enemy to bury him under an army without any first strike capability or combat heal.
Alternatively, I would like to see one of the Illian rituals, possibly the Deepening but that might come to early, or else the Draw, grant an additional Ice mana. He has 30 Ice affinity so with 2 Ice mana it wouldn't matter if he's fighting a 20 strength C5 hero with magic resist (remember Avatar halves magic resistance), he is NOT going down.
Oh, and while other tweaks such as cannibalism or ice mana are more important, I think it's absolutely critical that he gets March. Really, Avatar should grant March and Cannibalism, in fact I think I'm going to change that right now.