I know you didn't want to solely limit it to the 3rd age, and the Nazgul, but here is why I will limit any assassination attempt to the Witch-King and Sauron (you may argue the Nazgul - but there's 8 of them anyway).
The purpose of any assassination is to take out the leader, or an important figurehead, which will demoralize and send your enemy into disarray. It would be pretty useless, and ineffective to try and assasinate someone like Gothmog or the Mouth of Sauron. Gothmog was 2nd in command (behind the Witch-King), but bottomline is he was a lower-level officer, who cares if he dies...the army still would have the Witch-King (unless of course you assassinate the WK and Gothmog...
). But Gothmog is expendable. So, is the Mouth of Sauron, he may be the "Lieutenant of Barad-dur" but his death means nothing if Sauron is still alive. All the Mouth's purpose at the Black Gate was to serve as a decoy to spring Sauron's trap. He goes out, tries to demoralize his opponents by showing the Mithril shirt, and then runs away after a couple of insults. He is nothing more than Sauron's decoy, and as long as Sauron is still around, he can always find another "Mouth" to be a decoy.
Now the armies are clearly affected when Sauron (or well the Ring) and the Witch-King are destroyed, so those are the ones you would need to target for an assassination attempt. You may argue one of the other Nazgul, as they were also leaders to some degree, but it is made clear the Witch-King is their leader, and they are a lot stronger when the Witch-King is around - and of course we know what Sauron's death did to his army, they went nuts, fled, slew themselves or surrendered.
Trying to assassinate a lower level commander is useless, unless you take out the head hanchos, because the lower-level guys can always be replaced. I mean would you try to take out William Wallace or his lieutenant? Which will have a more devastating impact on the army?
So, why didn't they try to go after Sauron or the Wiki? Well, Sauron's pretty holed up and well fortified in his tower. He was not going to make the same mistake during the Last Alliance and place himself in a position to be killed (which is probably why he has a "Mouth" by the time he returns and starts rebuilding in Barad-dur). And I'm afraid that slaying the Witch-King may be harder than shooting him with an arrow.
When he and Gandalf faces off, even though I would argue that it's clear Gandalf is far more powerful than the Witch-King, I still don't think Gandalf could have killed him, because not everything in Middle-earth can be taken down with shear force or power. The Nazgul were bound to Sauron, and the Ring, as Gandalf tells Merry about why they were not killed by the flood, the Nazgul "rise and fall" with Sauron. How do we know Gandalf is probably correct...when the Ring is destroyed the remaining Nazgul go
*poof*. (
Mount Doom)
Now, there does seem to be a little caveat to the Witch-King and that are the Blades of the Westernesse, which the hobbits find in the Barrow. These blades were specially designed, and wound with spells to defeat the Witch-King, who was their mortal enemy. So, if there was an assassination attempt, I would guess you would have to use one of the Barrow blades - so maybe the Westernesse were planning an assassination.
Anyway, I wonder how many of these Westernesse blades there were, and who knew about them. The way we find out their effect on the Witch-King is Merry's stab, and Tolkien (as the author) tells us their history. But what characters in the story knew? When Frodo stabs the Witch-King and just gets a piece of his cloak, Aragorn says that's all his blade would have done, because all blades would perish that pierce the Witch-King (
Flight to the Ford)...so Aragorn didn't know about the blades' special power. Would someone else?
Now of course this entire mention of the Barrow blades might be useless, considering The Witch-King was stabbed in the face by Eowyn's "normal" blade and hence he was killed, but that was only because the Witch-King was rendered useless after being stabbed by Merry's blade wound with spells, specially designed to be the "bane of Mordor."
I have an interesting question though, what about Sauron's rather indirect assassination? And that is what about his hand in causing the death of Denethor? When Denethor was snooping around in the palantir, Sauron saw a perfect opportunity to weaken Gondor, his strongest enemy, by messing with Denethor's mind. Could that be called an assassination in a way?