But I went over the transcript, and I must concede it is explicit in the episode that Gary does have knowledge of the future. His full line in the transporter room was, "That's impossible. In this time period, there weren't -- Humans with a Vulcan? You're from the future, Captain." His use of "weren't" makes it pretty clear he's acquainted with thinking of the 1960s in the past tense. Moments later, he says of his employers' world, "Even in your time, it will remain unknown." That's not just a conjecture or extrapolation, it's a statement of certain knowledge.
So we can conclude that, while Gary was native to the 20th century, he and his employers did have direct knowledge of the future. Thus they undoubtedly had time travel in their repertoire.
Indeed, DC comics ran with this idea for a movie-era encounter between Kirk and Gary, with plot elements that seemed to lead into the political situation with the Klingons in TUC. Gary is an "intervention" agent working for a group called the Aegis, who can travel through time as others do through space. His mission, and that of other agents, is to ensure that the histories of their planets are not altered by outside influences and that potentially lethal conflicts don't destroy them. But some interventions fail, and this led to a group of agents going rogue and trying to destroy the Aegis.