I'm not 100% sure about this, but I think the answer is that Tolkien's published writings give no clear indication either way. It's important to note that the books focus almost exclusively on the north-west of Middle-earth, and there are large regions east of the Sea of Rhun and to the south and east of Umbar about which we know very little. There is no way to determine if any elves live there, or exactly what they look like. For a more definitive answer, we would need:
(1) A description of an elf as having dark skin.
(2) A statement from Tolkien (writing as an 'all-knowing narrator') that such elves do or do not exist.
Now we face the problem of looking for statements that may or may not exist (and that could be worded in many different ways) in a large body of work.
It seems to me that the best places to look for (1) are sections of the text in which Elvish characters appear for the first time, for example descriptions in the early parts of the Silmarillion (especially in Of Eldamar and the Princes of the Eldalie), Elrond and the Wood Elves in the Hobbit, Gildor, Glorfindel, Arwen, assorted elves at the Council of Elrond, Haldir, Galadriel and Celeborn in LotR. In most of these cases, elves are either described as fair, or there is no mention of skin tone at all. Of course Tolkien often uses 'fair' to mean beautiful. For example, it's not clear exactly what is meant when Gildor's group is described as 'fair' in Three is Company, since their speech is also described as 'fair'. On the other hand, Ar-Feiniel is described as 'pale' in Of Eldamar and the Princes of the Eldalie, so she must have been paler than (most) other Noldor elves, meaning there is at least some variation in skin tone. Similarly, Arwen is described as having white arms, which would be an odd statement if all elves had the same. However, I found no description of an elf as having dark skin.
Looking for a general statement about the exsitence of dark-skinned elves is also difficult, but we can make some progress. First of all, a statement that all elves are fair-skinned must refer to the elvish race as a whole, so the most likely places are Of the Coming of the Elves and the Captivity of Melkor (since there the elves are all together), or in some general description in a location such as one of the letters. I cannot find any such general statement about skin tone (but someone else did; see below). Another approach is to note that Tolkien sometimes describes darker skinned men as 'Swarthy' (e.g. Of the Ruin of Beleriand and the Fall of Fingolfin; and Hirgon's remark in The Muster of Rohan). The indices to LotR, the Silmarillion and the Unfinished Tales have no entries for Swarthy Elves, and there is no entry in the complete Guide to Middle-earth (CGtM, which is generally quite comprehensive). Likewise, I can find no mention of Swarthy Elves in the History of Middle-earth, or the letters (though there is a mention of a Swart elf; again, see below). There is also an isolated (and somewhat derogatory) description of a darker race of men in The Battle of the Pelennor Fields. However, neither the indices nor the CGtM mention black elves. So, after a considerable (though not exhaustive) search, I found no statement that proves or disproves the existence of dark-skinned elves.
Quotes and further information from comments
Some quotes I missed have been pointed out by other users. @Tristan noted that Maeglin is described as 'swart' in book II of the Lost Tales (The Fall of Gondolin):
Less fair was he than most of this goodly folk, swart and of none too
kindly mood, so that he won small love, and whispers there were that
he had Orc's blood in his veins, but I know not how this could be true
A similar description appears in The Shaping of Middle-earth (The Quenta):
He was swart but comely, wise and eloquent, and cunning to win men's
hearts and minds.
However, the Silmarillion (Of Maeglin) clearly states that his skin
was white. I can't find any discussion of this change, but I think
CJRT's edits to the Silmarillion were made mostly to keep names,
family trees, etc. consistent and it seems unlikely that it's due to
anyone other than JRRT himself.
@Eugene, pointed out the following, in LotR appendix F part II:
They [elves] were a race high and beautiful, the older children of the
world, and among them the Eldar were as kings, who are now gone; the
People of the Great Journey, the People of the Stars. They were tall,
fair of skin and grey-eyed, though their locks were dark, save in the
golden house of Finarfin.
Since the Eldar and the Avari come from the same three tribes, this
appears to apply to all elves, and looks (at first glance) to be
definitive. However, it can't apply to all elves, for two reasons.
First, Thranduil (of the Teleri) is described as having golden hair in
The Hobbit (Flies and Spiders, pointed out by @Amarth). Second, the
very meaning of the word Vanyar (given in the index to the
Silmarillion) is 'golden-haired'. Christopher Tolkien discusses this
text in his comments toward the end of the first chapter of Lost Tales
I. He writes
... these words describing characters of face and hair were actually
written of the Noldor only, and not of all the Eldar ... I am unable
to determine how this extraordinary perversion of meaning arose.
Later, in the Peoples of Middle-earth (The Appendix on Languages),
CJRT revised his opinion, writing
... my father carefully remodelled the passage in order to apply it to
the Eldar as a whole, and it does indeed seem 'extraordinary' that he
should have failed to observe this point [the golden hair of the
Vanyar]. It seems possible that when he re-used the passage in this
way the conception of the golden hair of the Vanyar had not yet
However, in the subsequent note (numbered 4), CJRT points out that a
description of Idril Celebrindal (in Of Maeglin) from 1951 mentions
her having golden hair due to Vanyar heritage and predates LoTR, which seems to contradict his earlier suggestion.
How to read this riddle? One of Tolkien's own literary devices is that he
obtained a copy of the Red Book of Westmarch and acted as
translator. LotR appendix F II is written from the translator's perspective, so it
makes no sense for it to contain information about any aspect of
Middle-earth unless that information comes from the Red Book
itself. In other words, we need additional quotes and (in my opinion)
should not rely the translator's assertion alone, especially as it is
wrong about hair colour. Why should we assume it is correct about
I'm inclined to stick with my original conclusion: we don't know.
If dark-skinned elves exist, they are probably located in regions of
Middle-earth that don't feature much (if at all) in the books. If someone can find a more definitive statement from JRRT then I will stand corrected (or perhaps argue about its canon status!).