Even though I agree that it would make some sense that Gothmog was a Nazgul, but, somehow, I can't imagine him as such, just like Legate.
He surely was no simple orc, maybe some mighty orc captain, but I doubt it. He would have had the strength and authority needed, but he still would have been no more trustworthy than any orc.
I always imagined him as some sort of Black Numenorean, or some other human of a nobler kind long under the power of Sauron. (Earnur?
)
What I think we can rule out is that he was something else. I mean, come on, just look at how much joy Tolkien obviously had when he described such things, the description of the Fell Beasts, for example. If Gothmog was something else what we didn't knew then, he would have told us and he would have described him to us, gloomy and vaguely, and the lines would have been little gems of the trilogy.