IMHO it is perfectly possible that the Constellation in "The Doomsday Machine" was a starship of a non Constitution class.
When they search for the missing starship Constellation Spock says:
I have it on the sensors, Captain. By configuration, a starship stopped in space. She appears to be drifting.
[1]http://www.chakoteya.net/StarTrek/35.htm
Note that Spock doesn't say that the configuration matches any particular CLASS of spacecraft. He says that it matches a TYPE of spacecraft, a starship.
A TYPE of craft is one which performs a specific function, such as a battleship, an aircraft carrier, a tugboat, a private jet, a news helicopter, an airliner, a moon lander, etc.
A CLASS of craft is a group of craft of a specific TYPE which are all built to almost totally the same plans with only very minor variations.
The Iowa class battleships were one of dozens of classes of battleships which were built, for example.
So in Kirk''s era the Starfleet TYPE of starships has at least one CLASS, the Constitution class, and there may be several other classes of starships. Thus identifying a ship as being of the starship TYPE may not necessarily identify it as being of the Constitution CLASS of starship.
I have read that a consumer model kit of the Enterprise was used to film the Constellation and that it was not totally accurate and there were slight differences in configuration. When they look for the auxillery control room on the Constellation Kirk walks right past it before spotting Matt Decker in it. So some of the internal arrangements are different on the Constellation.
Thus it is uncertain whether the differences between the Enterprise and the Constellation are differences between two different ships of the same TYPE and the same CLASS, or between two ships of the the same TYPE but different CLASSES.
Furthermore, nobody knows the "frame story" which explains how knowledge of future, 23rd century, events was transmitted to the creators of Star Trek in the 1960s. And without knowing the "frame story", nobody can know how much of Star Trek is accurate.
Thus, so far as we can know, it is perfectly possible that the creators of Star Trek saved special effects money by deliberately making other starships seen in TOS look like Constitution class starships even though they knew those ships belonged to different classes.
So the common opinion that all starships seen in TOS were Constitution class starships is perfectty possible but has insufficient supporting evidence. And this I suggest that the Constellation MIGHT POSSIBLY have been the first non Constitution class starship seen in TOS.