How about keeping him as just a regular Kobold?
The party has to fight his champions and are expecting a terrible and powerful villain but it might make a refreshing change to make the villain a political mover and shaker and not a combat powerhouse. Such a villain would work by manipulating others. Once he became aware of his powerful enemies in the player characters, he would rig the game against them. So for example, he would resort to kidnapping to blackmail the party to change their intention of toppling him. He would bribe individual party members to turn against one another. He would make them think that they've already beaten him. He would leave false trails to his other enemies to make it appear that they are the ones behind the atrocities and not him. In other words... he'd be a devious little devil that would prove to be much harder to remove than a high level tank/mage that must be brought down through combat... especially if killing him is not an option and he must instead be brought to trial...
