He wasn't an Orc, as Sauron wouldn't trust command of his main force to an Orc.
He couldn't be a Nazgûl, as Gothmog is an Sindarin name, and all of the Nazgûl are either Númenórean or Easterling Men, with names derived from their languages.
He is most possibly a Black Númenórean. We have precedent for a lieutenant to be a Man. Most of you remember the Mouth of Sauron, right? He was the Lieutenant of Barad-dûr.
I'm pretty sure he was a Black Númenórean.
To those interested, here is where the whole thing started.