I like the mechanic too; but I think that it is potentially too easy to level him.
Rather than making him weaker and thus less useful as a unit in his own right (which would work to a degree) I think that slowing the rate at which he gains xp could help, if that's possible. Even if you did that, eventually he'd get to combat V, and I find that a bit strong - if you don't think so, that's fine though. I was thinking maybe a line of golem promotions (Golem I-V) which gave lesser strength bonuses like 10% or so would be less severe, but I realise that is adding a whole lot more promotions to the game.
Also, I think that the base golems could be overpowered; wood, iron and clockwork are relatively strong for their respective eras - I know this is because they can't normally level, but with the Barnaxus mechanic... they're very strong. And even after you kill Barnaxus, they're still quite strong against relatively unpromoted units from other civs, especially the iron golems, and clockwork. Perhaps you could downgrade the iron and clockwork strengths by 1-2?
Incidentally, what I've seen of the AI using Barnaxus wasn't that good - for such an important unit strategically, he shouldn't be be left alone in a square, especially not going on the attack.
Finally, I was thinking that maybe if Barnaxus was killed, the player should have some way of continuing his powers; that way you could reduce the strength of the golems and be less concerned about a Luichurp player being overrun. What I was thinking was a national wonder along the lines of "Ode to Barnaxus" or something like that, which granted all golems some or all of the combat promotions that Barnaxus had, and at least combat I (or golem I if you had that). Probably not up to combat V though, as that would make it unfair to others who had hunted Barnaxus to hamper the Luichurp army.
Let me know what you think, I really enjoy the mod and the way you listen to the community input.