quaesisse se cuius nationis esset: respondisse nescio quid perturbato sono et voce confusa; non intellegere se linguam eius: nec Graecum esse nec Romanum nec ullius gentis notae.
esse in the final clause could have two different subjects. The first is Claudius, with the clause expressing a conclusion drawn from the preceding description of the messenger’s interrogation; that is, Claudius is neither Roman, nor Greek, nor of any other known people.
Alternately, it could be taking the linguam from the previous clause as its subject, with the three possibilities raised refering back to it, emphasizing the unknown nature of Claudius with the fact that the language he is speaking is not even important enough to have an adjective in Latin.. Also note that Graecum and Romanum are in the accusative, while ullius gentis notae is in the genitive. This may be a simple possessive genitive referring back to linguam, or a case usage retained from earlier Latin to mark the inferiority of the words put into the genitive relative to those in the accusative.
tum Iuppiter Herculem, qui totum orbem terrarum pererraverat et nosse videbatur omnes nationes, iubet ire et explorare quorum hominum esset.
The use of explorare is interesting in this context, given its connection to the Roman army’s exploratores, its scouts and spies. The implication that Hercules is intended to spy on Claudius to learn about him is particularly amusing given that Hercules is explicitly stated to be a man of minime vafro in 6.1.
quorum hominum could be a possessive genitive or a genitive of description, but requires a bit of wrangling to sound natural in English. Literally “of which people he was,” it works better if translated as “who his people were” or more loosely “what country he was from” or “where he was from,” the sense of which is provided in the assertion that Hercules is being sent for his knowledge of various nations. The fact that this is the question that Hercules is sent to answer supports the interpretation of the preceding clause as addressing Claudius’ nationality rather than the language he speaks, in my opinion.
The use of homo instead of vir, which would normally be used of Roman men, is another calculated insult against Claudius.
Graecum and Romanum are not in the feminine, which helps your interpretation. Sometimes Latin does this, though, with the gender of an adjective being influenced by something else so much that the usual rules don’t apply. But here I think it’s more likely to be referring to Claudius, as you said.
In the OLD under Graecus, definition 2c, it says that the neuter form Graecum can be used as a substantive to mean “Greek speech, Greek”, by which I believe they mean the Greek language. Thus it seems that Greacum here could refer to the language. There isn’t a similar definition under Romanus or Latinus, but perhaps by analogy Romanum could mean the Latin language.
It seems to me much more likely that “nec Graecum esse nec Romanum nec ullius gentis notae” refers to the language Claudius is speaking rather than to Claudius himself.