Who were the Ringwraiths?

[Halbarad]

In Of the Rings of Power and the Second Age it says that after Sauron had gathered the Rings of Power to himself he

dealt them out to the other people of Middle Earth, hoping thus to bring under his sway all those that desired secret power beyond the measure of their kind

so it was Sauron that dealt them out.
In the Silmarillion Tolkien wrote

...In the south and in the further east Men multiplied; and most of them turned to evil, for Sauron was at work.

.

We also know that the Harad-men and the Easterlings worshipped Sauron; he was their overlord, so I would suggest that more than one of the Nazgul were Easterlings or Southerners, tribal chieftans, warlords, men of power at any rate. We don't know how large the eastern areas went, but they had a lot more men than Minas Tirith did, as we saw in the battle before the Morannon, so probably large. This is all a long way of saying I think that the Nazgul (apart from the Numenoreans) were of eastern and southern extraction