Give him an aura that affects his allied army. The Lieutenant gains significant damage reduction against all damage based on the number of allies he is currently affecting with his aura, and his allied units in the aura passively gain health over time or have increased attack speed or some other bonus you feel is relevant. The way to defeat him is to reduce his damage reduction to a point where damage against him 'sticks' by either killing his troops (in the aura where it's harder or out of it where it's easier) or crowd control/taunt/push-ing his units out of his aura long enough to get in some serious damage on the boss.
I would scale the resistance such that he's totally immune with slightly less than of his forces in close range, so killing like 2 of them makes him only have 98% reduction or something. As the number of allies diminishes this reduction becomes 90..85..80..75..65..50..30..5..0 so it is more effective the more you kill. Clue players into this mechanic by popping up big "IMMUNE" floating text when a damage instance against him is fully prevented, and perhaps pause the battle briefly to play a 5 second cinematic of him saying something when the necessary number of units to break the 'total immunity' has been reached.
Giving him damage reduction rather than the invulnerable ability means that while he can't be damaged players can still hold him in place with crowd control, debuff him, or cast other spells that require a target. They will also have to micro a bit to make sure their forces aren't wasting attacks on the boss. A smart player will naturally think to separate some of the boss's weaker force units and kill them.