The LotR does not mention any names of the
Nazgûl. In the UT we can find the name
Khamûl, along with references like "Black
Easterling" or "Shadow of
the East" (you have found that already), so I think that his eastern origin is sufficiently confirmed.
However, whether this knowledge comes from canon text is debatable. You have mentioned correctly that several versions of the tale “The Hunt for
the Ring” are published; Christopher
Tolkien himself was not beyond some doubt which parts were to be considered as “final” (if such a word is applicable at all, in JRRT’s literature).
BTW (not related to your question), as regards the origin of the other Nazgûl, their leader was the Witchking of
Angmar so we know at least who he was (yet without a name). In TS you can also read this:
"[...] it is said that among those whom he ensnared with the Nine Rings three were great lords of Númenórean race."