I like the regicide idea
Its very much a capture the enemy flag rather than wear him down and destroy everything which should promote a wider range of strategies, and ability to return from a weak position
My only criticism of civ in general, including ffh2, is that the end game is so often long and drawn out, and the game ceases to be fun a long way before the end. Having a winning condition that eliminates players by taking out one unit is a golden idea.
What would happen to a player's cities and units when a player is ousted? Given to the killer, made barbarian or just deleted? I'm thinking making the civ an AI controlled vassal of the victor could work well.
In terms of the rex himself, it would be interesting if in his development there was a trade-off between being tougher to kill and being more powerful. Someone wanting to prioritise his survival could over time increase his defence, make him invisible, give him fast movement, escape, etc. Alternately you could promote him to be an effective aggressive unit, to give a boost to culture, science, reduce maintenance costs, etc.