According to the Wikipedia article on this topic, The Picture of Dorian Gray was "first published complete in the July 1890 issue Lippincott's Monthly Magazine." That same year, Merriam-Webster published its massive Webster's International Dictionary—a volume that lists three definitions in its entry for fatality:
Fatality n. ... 1. The state of being fatal, or proceeding from destiny ; invincible necessity, superior to, and independent of, free and rational control. [Example:] The Stoics held a fatality, and a fixed, unalterable course of events. South[ey]. 2. The state of being fatal ; tendency to destruction or danger, as if by decree of fate ; mortality [Examples:] The year sixty-three is conceived to carry with it the most considerable fatality. Sir T[homas] Browne. *By a strange fatality men suffer their dissenting. Eikon Basilike. 3. That which is decreed by fate or which is fatal : a fatal event. Dryden.
Of these three definitions, the one closest to what Wilde seems to have had in mind in his sentence "There is a fatality about all physical and intellectual distinction, the sort of fatality that seems to dog through history the faltering steps of kings" is the second one—a "tendency to destruction or danger." If so, Wilde may be asserting that a connection exists between being exceptional in physical or mental abilities and being in greater danger of destruction, as if at the hands of jealous Fates. Wilde seems to suggest that, by standing out from the safety and anonymity of the crowd (or the average), one exposes oneself to a heightened risk of being singled out for ruin.
Neither of the online Oxford Dictionaries definitions that you cite covers this sense of fatality at all well, and I don't think it is accurate to describe the "state of being fatal ; tendency to destruction or danger, as if by decree or fate ; mortality" meaning as obsolete or archaic. It seems to me that I encounter fatality used in this sense too often to consider it rare—but I do read a lot of old books.
Merriam-Webster's Collegiate Dictionary, eleventh edition (2003) also yields more definitions of fatality than you might expect from the online Oxford Dictionaries' treatment of the word:
fatality n ... (15c) 1 a : the quality or state of causing death or destruction b : the quality or condition of being being destined for disaster 2 : something established by fate 3 a : FATE [in the sense of 'destiny"] b : FATALISM [in the sense of "the doctrine that events are fixed in advance" of their happening] 4 : the agent or agency of fate 5 a : death resulting from a disaster b : on that experiences a fatal outcome
Of these definitions of fatality, 1(a) seems the closest to the sense that Wilde had in mind in his sentence.