I think New Jack City qualifies for this thread. All I can remember is some dude on his knees asking someone if he was his brother’s keeper before he gets tapped in the head.
Not quite what the thread is asking for, but it fits the spirit in that it shows the villain’s badassedness.
The Usual Suspects: A tale is told of how hardcore Keyser Soze is, to the point where some of his enemies hold his wife and kids to threaten Soze. Soze kills his wife and kids in front of them to prove how that sort of stuff doesn’t work on him as blackmail, and then lets one of his enemies escape to spread the tale.
Paraphrasing
"It’s not hard. You go around town, and if you see someone you don’t know, you kill him. See that guy?Points at a random goon I don’t know him. Look, he has a gun."Shoots him
Nope. Thulsa has just told Conan the Riddle Of Steel- “What is stronger than steel?”. He tells the woman to jump “Come to me, my child.” in order to demonstrate the answer ‘Flesh is stronger than steel.’
And if we add in Gabriel Byrne’s crew as henchmen (…they are working for him), we can note that he wacks all of them too.
Plus the former henchman who had ratted him out…
General Ouromov in Goldeneye.
Quite early on in the film (in that 5 odd minute part of every Bond film) he dispatches a soldier under his command who had just fired a shot at some gas canisters Bond is hiding behind.
Maybe Thulsa Doom didn’t do it, but Sidney Poitier’s character did in the Viking/Muslim epic The Long Ships: http://www.imdb.com/title/tt0057259/
(Yep, there was one before The 13th Warrior)
The idea of a powerful ruler having one or more of his underlings kill himself to demonstrate loyalty has a long history, going back to the medieval days if not earlier.
This whole idea of The Bad Guy killing an underling is a fine and cheap way of demonstrating that The Bad Guy is, well, bad, that he has no respect for human life, and implying that if he can kill someone faithful to him, imagine what he’ll do to the hero opposing him. It’s been overdone. It’s even in kid’s cartoons (Rattigan offs one of his drunken followers in Disney’s The Great Mouse Detective.
It’s such a cliche that fun was made of it in the 1960s. In one episode of The Man from U.N.C.L.E. Napoleon Solo tries to “turn” a T.H.R.U.S.H. employee who’sd about to be executed at his own retirement dinner by letting him in on that secret. (Do S.P.E.C.T.R.E. henchmenm have retiremernt dinners? Do they have unions?)
Ummm, yeah, isn’t that what I said? Thulsa Doom told one of his followers to jump off a cliff and she did.
The whole “flesh and steel” thing was Thulsa Doom mocking Conan. He said that he used to be a warrior, like Conan still is, and thought that he was powerful because of his personal fighting ability (steel). But then he realized that real power comes from being able to command other people to do your fighting for you. So even though he’s personally unarmed (flesh) he’s much stronger than Conan because he’s got an army of followers. And then he has one of his followers step off a hundred foot cliff to demonstrate how his followers will do anything he says.
Hopper (A Bug’s Life) buries two of his cohorts in hundreds of nuts to demonstrate that one can be defeated by the collective effort of numerous smaller opponents, i.e. the ants that the grasshoppers have been subjugating for some time.
Actually, that whole scene of the grasshoppers lounging in their (Mexican?) digs is unnecessary and should have been cut. It doesn’t really add anything to the movie.
I’m convinced the whole scene was simply structured to work in the joke about the PuPu Platter.
Kinda like the unnecessary scene in Jurassic Park where Ellie looks through the droppings of the Triceratops - serves no purpose other than it lets Malcom say “that is one big pile of shit.”
How about heroes who intentionally kill one of their henchmen, in order to get at the bad guys? There’s remarkably few, the only one I can think of is the tv show “24”, where (Season Three spoiler):
Jack Bauer kills the head of CTU as a demand of the terrorist, who threatens to release the supervirus if Jack doesn’t comply.
And of course there’s Goodfellas, The Godfather, The Sopranos, and many other gangster films…except some people consider them villains instead of heroes, I guess. 
In the Wesley Snipes action flick Passenger 57, the Bad Guy Boss shoots one of his henchmen after failing to kill Snipes…calling him “Incompetent.”
Neither Banquo nor MacDuff were particularly enthusiastic followers, but MacBeth had been formally crowned as king, and they would have sworn fealty to him at the coronation ceremony. I think he at least threatens to kill the flunky who informs him that Birnham Wood has come to Dunsinane.
Richard III is a better example. Drowning his brother in a barrel of wine, and turning against Buckingham almost the moment he is crowned.