Nincompoop is, according to one source, (a book titled “Lock Stock and Barrel”), derived from a phrase meaning “innocent fool.” The reason given is that “Nin”, is a shortened version of the name Innocent (similar to Edward being shortened to Ned), and the old Dutch, “poep” meaning fool (although it also means “shit”).
Another definition is it is a corruption of “non compos mentis” which means, “not sound of mind.” Although I doubt this is exactly right since although it would account for the “nincomp” part, the “poop” seems to have come from nowhere.
There may also be a French element, the word “Nicademus” means fool, so it could mean “foolish fool.”
The first recorded use was in 1706, but there have been uses prior to that with the spelling “Nicampoop,” which may or may not be the same word. Today it tends to be a fairly snobbish insult, and often refers to an underling, such as a servant or waiter, although can be applied to a superior such as the president or prime minister. Not that I’m saying anything…
Sources: http://www.takeourword.com/et_n-p.html#nincompoop, www.briggs13.fsnet.co.uk/book/n%20&%20o.htm and the book “Lock Stock and Barrel”
Monkfish says: For what it's worth, the OED records a use from 1676 ("nicompoop") and says the word's "of obscure origin" and "probably only a fanciful formation". ("Johnson's suggestion of non compos does not agree with the earliest forms.")