So how about a creature that roams the board and attacks things. The movement would be random and its strength would set to 8 at the end of its turn. It would not actually control territory, spaces it leaves would be 'empty' with no enemy in them or possibly a 1. Behemoths would always have both boosts, they are meant to be mostly unkillable. You would select an option to turn them on, possibly a selection from the Zodiac signs or it could be random.
each Zodiac could give a certain prize when beaten. For instance Ares could give a couple of attack boosts or Leo could make your current border tiles gain Defense boost. Other less obvious one like Libra could make all border regions have equal amounts of troops and Aquarius could 'wash away' all boosts on the board. Additionally, a piece of art could be displayed depicting the legendary creature when it was killed or attacked. There could also be a map pack based on the zodiac signs.
The idea being a very simple NPC creature that moves around randomly attacking things, maybe with a preference to attack what ever attacked it last and give a neat boost when killed, probably something that benefited the player that killed it.