[Meneltarmacil]

I appear to have made an error in my previous post. I found out that the Rohirrim did not live in the upper vales of Anduin at the time the Nine Rings were given. It seems they were actually living east of Greenwood the Great (later Mirkwood) in Rhovanion and didn't move to the vales of Anduin until later. So the whole theory I put forth about Angmar is definitely wrong. Still, one of the kings/leaders of Rhovanion may have become a ringwraith.

So the possible homelands of the Nazgul are:

Numenor and colonies (3 confirmed)
Rhun (1 confirmed, Khamul)
Harad
Rhovanion, or future Rohirrim
...and possibly more, but these are the only ones that I think could have had kings or lords at the time.