Since the plot is utterly nonsensical as such, any interpretation deviating from it must be preferred.
No, the dialogue does not establish Kodos as the governor of the outfit before the coup. And we have every excuse to assume that "Kodos" isn't a real name, but rather a nom de guerre
for somebody obsessed with power and law.
The thing is that Kodos was known to 8,000 people at the time of the massacre, and to the entire universe afterwards: there'd be no point in having "witnesses capable of identifying him", either from the point of the law (physical evidence, recordings and the like would suffice) or from the point of Lenore Karidian (eliminating the nine would accomplish nothing). However, people would presumably arrive at the colony in smaller groups; if "Kodos" is a recent arrival, then there could well be just nine witnesses to who he "really" is.
The plot is full of other illogic as well, further affecting the interpretation of Kodos. The writer suggests ambiguity in whether the Executioner's ruthless decision was a rational one - but doesn't realize that it never could be. Killing half the people to allow the other half to survive is not viable in the scenario outlined: if there are going to be scheduled supplies, remaining food can be stretched essentially indefinitely, and if there are not, everybody will die anyway. So we must argue that Kodos took power solely in order to be able to kill 4,000 people. This is not something a madman like that would spend years quietly waiting for, in the position of Governor...
A man who comes, kills, and goes would thematically fit James T. Kirk also being the sort of boy who travels a lot. The other option, of him being one of the actual colonists, is the one where we run into problems regarding his parents or custodians. Although of course that's also a path worth exploring.