I only encountered a Combat Master once on my playthrough, but it was after I had acquired the Brand skill and one tactic I found to work was to brand nearby Uruks and have them fight him. The damage they themselves did to him was inconsequential, but while he's fighting them, you can get behind him and he's vulnerable to Wraith Stun from behind. Of course once he's stunned you can damage him multiple ways.
Also, as wr4ith says in the comments, if he has a Fear and you exploit it, he's more vulnerable to other tactics.
Wraith Flash normally does the trick. Just build up the combo so you can wraith flash, just don't use the combat execution or combat brand because combat master deflects those. But not Wraith Flash. It takes time, but the higher the combo the more damage it does.
If you already have the Lethal Shadow Strike skill, and provided that the Uruk captain is not invulnerable to ranged attacks, you can keep on using Lethal Shadow strike on him (consumes elf-shots). If you run out of elf-shots, you can build up your hit streak on the Uruk captain (but don't finish the combo), and then combat drain/brand other Uruks.
I ran across a tough uruk who was immune to combat finishers, stealth, ranged attacks and a whole heap of other bad effect that made him seem invincible. I had to keep this level 20 ledgendary captian from killing my warcheif and fight off everyone until i could run and tackle him a few times before he went down which was another way to deal with overpowered RNG if anyone runs across the issue.