One can begin by separating out the question of which qualities--good looks, brains, or whatever you like--qualify as being "not nothing" (more than nothing? less?) That leaves us with the question of "counting negatives" and the related matter of "correct idiom".
In searching for the correct idiom, intuitively we have a sense of "that sounds right" or "that doesn't sound right", and though such intuitions can lead us astray, they nevertheless point to deep-seated features of the living language.
The way you present it, it seems to me that your phrase and the improved version you're looking for would both be written usages, since my instinct tells me that one would rarely, if ever (though perhaps in certain workplace situations like this?) speak a phrase that started "not for nothing...", since whether one was referring to oneself, a second, or third person, it would sound a little clumsy, or overly formulaic, or just not quite spoken-idiomatic.
By contrast, you might say "I didn't get this job for nothing" or even "I didn't get this job because of my good looks".
"Not for nothing" may be a double-negative in the technical sense, but because it exists as widely-used (more or less) phrase, and semantically the two parts are both "empty negations" whose meaning is simply to negate, or "the absence of anything", these two negatives together have a symmetry or balance to them that other phrases ("not unproblematic", say) do not possess. Because of this, you should aim to employ the "not for nothing" (which seems to be the phrase you want most to save) in a pleasing fashion, and without the need to add additional negatives.
My amended version of your sentence would be: "Handsome, intelligent, and full of potential, not for nothing was he the director of this organization". A single, crisp, and even balanced/symmetrical "double-negative". The placement of the first clause modifying "he" at the front has the right idiomatic feel. Thus would I write.