The concept of a third sex is as old as writing. In Greek myth there's the figure of Hermaphroditus. In the Sumerian creation myth, the goddess Ninmah creates an intersex human from clay:
Sixth, she fashioned one with neither penis nor vagina on its body. Enki looked at the one with neither penis nor vagina on its body and gave it the name Nibru [perhaps = eunuch], and decreed as its fate to stand before the king.
The idea recurs in other ancient cultures; see Wikipedia's third gender article for many more examples.
A few notable early examples in science fiction:
In A Voyage to Arcturus by David Lindsay (1920) some of the characters belong to a third sex:
Nowadays there are men and women, but in the olden times the world was peopled by phaens. I think I am the only survivor of all those beings who were then passing through Faceny's mind.
The Last Men in Olaf Stapledon's novel Last and First Men (1930) have many sexes, though these are apparently organized into "male" and "female" sexes:
The traveller would recognize among us unmistakable sexual features, both of general proportions and special organs. But it would take him long to discover that some of the most striking bodily and facial differences were due to differentiation of the two ancient sexes into many sub-sexes. Full sexual experience involves for us a complicated relationship between individuals of all these types. Of the extremely important sexual groups I shall speak again.
In That Hideous Strength (1945) by C. S. Lewis there's a cryptic reference to the "Seven Genders":
The three gods who had already met in the Blue Room were less unlike humanity than the two whom they still awaited. In Viritrilbia and Venus and Malacandra were represented those two of the Seven Genders which bear a certain analogy to the biological sexes and can therefore be in some measure understood by men. It would not be so with those who were now preparing to descend. These also doubtless had their genders, but we have no clue to them. These would be mightier
energies: ancient eldils, steersmen of giant worlds which have never from the beginning been subdued into the sweet humilations of organic life.
Lewis didn't expand upon this, perhaps because he believed that it would be impossible to convincingly imagine a new sex. In a 1943 letter he wrote, "Try to imagine a new primary color, a third sex, a fourth dimension, or even a monster that does not consist of existing animals stuck together. Nothing happens." (This now seems rather defeatist. Maybe he should have tried harder.)