Examples of this do not seem to especially abound. Perhaps unsurprisingly, people tend to portray God or the gods to be whatever colour they themselves are, for better or worse. Nonetheless, as you have observed, such a phenomenon is not out of the question. Your mention of black Madonnas makes me think of 
the legendary Roman soldier St Mauritius [Maurice], who is remarkably popular in Europe (especially Switzerland), being the patron saint of Austria, as well as of one Spanish city, two cities in Germany and four places in Italy.
Conversely St George is the patron saint of Ethiopia.
AZTECA & MAYA
In late Aztec mythology the deities Ometecuhtli and Omecihuatl had four sons who were called the Tezcatlipocas, "Smoking Mirrors," who created all the other gods, as well as the world and humankind. Each Tezcatlipoca was a different colour.
The first, simply called Tezcatlipoca, was the Black Tezcatlipoca.
Quetzalcóatl, often occurring as the twin of the first one, was the White Tezcatlipoca. Regarding him and a few other pre-Columbian deities in the Americas there have been controversial theories claiming that their "whiteness" is a reference to Europeans (or even Atlanteans) whose arrival in the so-called New World antedates that of Columbus.
The third was called Huitzilopochtli, who was the Blue Tezcatlipoca; and the last was Xipe Totec, the Red Tezcatlipoca.
Essentially the same formula and myth recurs among the Maya with the Bacabs, who are the four sons of Itzamna and Ixchel, each placed by their grandfather the supreme god Hunab-Ku at one of the four cardinal points of the compass to support the structure of the sky. Each Bacab was a different colour: the Western one was black, the Northern one white, the Southern yellow and the Eastern red. These, however, are described as "iguana-like," so perhaps they don't count, unless perhaps they are iguana-like humanoids.
BUDDHISM from China
The four Tezcatlipocas and the four Bacabs bear a striking resemblance to an ancient Indian concept of four deities who each ruled over and guarded one of the four cardinal compass-point regions of the world. Hinduism and Buddhism arose from the same region, from peoples who venerated the same gods. In Chinese Buddhism these four world guardians, who would be readily recognisable to Hindus, are now called Sì Dà Tiānwáng, the "Four Great Heavenly Kings."
- Kubera [Kuvera], also known as Vaiśravaṇa, is the North King, who
rules over daemons called the Kinnaras and the Yakṣas. He is
yellow.
- Virūḍhaka is the South King, who rules the Kumbhāṇḍas. He is
blue, although sometimes depicted or described as green.
- Dhṛtarāṣṭra [Dhritarashtra] is the East King, who rules over
creatures called the Gandharvas. He is white.
- Virūpākṣa is the West King, who reigns over the Nāgas. He is red.
NORSEMEN
The Svartálfar
In his 2002 essay The Aesir and the Elves, William P. Reaves references the close association of the Æsir (who we know for sure to be deities venerated by the Norsemen) with the Álfar, "Elves," who we know tantalisingly little about but who it seems were a race of divinities related to both the Æsir and the Dwarves. According to John Lindow's Norse Mythology: A Guide to the Gods, Heroes, Rituals, and Beliefs, there are references in mediaeval Icelandic tradition to something called the álfablót, which translates to something like a "sacrifice to the elves." Based on this it seems that the Álfar were venerated (or "worshipped") in Scandinavia at some point. In Hávamál 159-160 "both Æsir and Álfar" are explicitly identified as tíva, "gods."
Snorri Sturluson is the only pre-modern mythographer who mentions any distinct classifications among the Elves, in that he says that some of them are "bright" or "white," and even dwell in heavens which are above and beyond the Æsir's home Asgarð; while some Elves are "dark" or "black." Lindow notes two instances of Snorri saying that the Dwarves live in Svartálfaheim, "Black-Elf World/Home." In Skáldskaparmál 35, Loki is forced to swear that he will get the Svartálfar (Black Elves, who in the Gylfaginning are "blacker than pitch") to replace the golden hair of Þórr's [Thor's] wife Sif, which Loki has maliciously or mischievously shorn off, with new locks that could attach themselves to her scalp and continue growing indistinguishable from ordinary hair.
The very next description is confusing in that it then has a family of Dwarves called Ívaldasynir (Ívaldi's Sons: a company name?), fulfilling this role of hair-supply. Reaves makes the case that Ívaldasynir are therefore Black Elves (= Elven Dwarves, or Dwarfen Elves?). They are significantly integral characters to the mythology since they end up creating not just a new head of resplendent hair for the thunder-god's wife but also some of the most important weapons and artifacts of the Æsir.
The Vanir (& the 'Whitest' of the Æsir)
Heimdallr, the watchman of the Æsir's home, Asgarð, bears some unusual features like (presumably natural) golden teeth, which give him the epithet Gullintanni. He is also, in the Gylfaginning, called Hvíti Ás, the "White Ás" [Æsir is plural of Ás], as though to suggest either that the Æsir are not themselves white or that Heimdallr's whiteness is really peculiar (starkly milk-white?). The poem Þrymskviða tantalises yet further in describing him as Hvítastr Ása, the "Whitest Ás," followed immediately by the statement that he possesses great foreknowledge "like other Vanir."
The Vanir were a tribe of gods who at some point rivalled the Æsir but were eventually assimilated by them, so that we have originally Van [singular of Vanir] characters like the god Njörð and his children becoming Æsir. It is most unusual, however, for a son of Óðinn [Odin], the chiefest of the Æsir, to be described as a Van, especially in the same passage that he has just been called an Ás.
The solution to this might be in Heimdallr's maternity, which per se is an anomaly in Norse mythology, as he is given his birth by nine mothers whose names are provided but whose origin is never explained. Conveniently, the sea-giant Ægir has nine daughters. Inconveniently, however, their names don't match those of Heimdallr's mothers. An alternative interpretation for the identification of the nine is that they are the daughters of the giant Geirröðr. The myths explicitly mention only two daughters of this giant but both their names are included in the list of Heimdallr's mothers.
Perhaps the discrepancies can be avoided altogether by linking the possible allusion to Heimdallr being a Van with his strange birth situation. Maybe the nine mothers of this Ás were actually Vanir. This would not preclude them from still being giantesses, as a few Vanir appear to have been just that. Pushing the link to a further conclusion could indicate that the Vanir were "whiter" than the Æsir. Maybe they were more immediate descendants of the frost giants and thus were literally snow-white(?). At any rate it would take us some distance beyond Lindow's resignation to the fact that
There are no indications of Heimdall's membership among the vanir. Nor has his whiteness ever been explained. (2001:170)
If this snowy Vanir theory is at all close to the mark, I suppose it would beg the question of what complexion the Scandinavian/Norse worshippers of the Æsir and the Vanir perceived themselves as having. In a lot of scholarship regarding Eurasian religions and myths, particularly in the 19th & 20th centuries, it has been quite popular to perceive the stories about conflicts between older deities and newer ones as indicating waves of invasions by settlers who usurped and assimilated indigenous cultures and stories into their own. If there is any merit to that, perhaps this is what the war between the Vanir and the Æsir represents: friction among at least two different people-groups. This, however, cuts against the usual grain of theories in this field, because in this case it would be a "white[r]" population being invaded by a "dark[er]" group.
Regarding the Elves who live above and beyond the Æsir, the Gylfaginning says that they are brighter than the sun to look at, which resonates with Benjamin Thorpe's translation of Heimdallr as hvítastr: "brightest" rather than "whitest," whatever that may mean. Maybe the Vanir are deities who are both more Elven and more Gigantic in nature while the Elves, especially the Svartálfar, are the familial link between the Æsir and the Dwarves.
Hel
In the Gylfaginning, Hel, or Hela, the gigantic goddess who houses and rules over the dead in the northern end of the universe, is described as half dark-blue (or blue-black) and half "flesh-coloured." This is generally interpreted to mean that half of her body has decayed (or suffered hypothermia in the frigidity of her ice-cold realm?), so perhaps this doesn't count as something exotically different from the complexion of the Norsemen, as Snorri is here probably imagining the same kind of discolouration that would happen to the average mediaeval Scandinavian corpse. I mention it mainly to indicate just one more instance of a Norse deity with a feature that is "fancier than red hair." Speaking of which, by the way, one of the daughters of Ægir is named Blóðughadda, "Bloody-Hair."
ANCIENT GREECE
Depending on which ancient Greek writer you consult, such as Herodotus, several if not most of the deities whom the Greeks worshipped had been imported into their country by Egyptians, Libyans, "Ethiopians," Phoenicians, Syrians and Mesopotamians in general. The myths themselves bear this out. An example of this is the African versions of Zeus.
One of these versions is mentioned by Lycophron and John Tzetzes, who call him Zeus Aithiops [Aethiops], a word which has come to be interpreted in a few different ways. It could mean "Glowing," "Fiery-Eyed" or "Burnt-Faced." The latter two translations can both be interpreted as references to dark complexion, such as that of the inhabitants of South Sudan, whom the ancient Greeks called Aithiopes. "Fiery-Eyed" has sometimes been interpreted as a reference to the stark contrast between the dark skin of the South Sudanese and the whiteness of their eyes' sclerae. William Smith's Dictionary of Greek and Roman Biography and Mythology translates Zeus Aithiops as "Black Zeus" and says that he was worshipped as far afield from Africa as the island of Khios, in the middle of the Aegean Sea.
