"I insisted that Mandela had a strong personality" is, in fact, the simplest of all the versions you've listed. It uses simple verb tenses, no gerunds, and you don't have to worry about the right preposition (as in "on Mandela having...")
One thing to note, however, is that even this sentence sounds a bit like you told Mandela that he should have a strong personality. That's because it looks like a subjunctive construction, which because you're using "had" happens to look indistinguishable from your intended meaning. One way to resolve the ambiguity is to say something like:
I insisted that Mandela was a man of strong personality.
Now this has the unambiguous meaning that Mandela had a strong personality, and you insisted on that fact. The corresponding sentence with a past subjunctive would've been:
I insisted that Mandela were a man of strong personality.
This means you insisted to Mandela (or to others) that he should have a strong personality.