Honestly, the 'it happened off-screen' explanation is the most solid explanation, and the only one we need. Even if we ignore post-Wrath of Khan books and writings. There is NO reason, in this instance, not to accept that their meeting 'happened off-screen'. Take into account that we are never told in TOS that Kirk has an estranged out-of-wedlock son, but there is nothing in the series that says he couldn't have had one, and the movie tells us he did have one. What's more, David was alive during the events of "Space Seed", and even before the first season, since it was only 15 years before Wrath of Khan took place. Nothing in the TV show or movies exists to contradict that David could exist, so when the movie tells us he does exist, we accept it. The character of Chekov was not referred to in Season One (and in the real world he hadn't been conceived or casted) BUT the movie tells us Chekov was on board and that he and Khan met at some point. That's really all we need to know. It only qualifies as a 'plot hole' if it is contradicted by some earlier onscreen reference or occurrence; like if they had said in TOS that Chekov was new to the ship the first time he appears in "Catspaw". The show never says that -- he just appears in an episode like any number of one-off or multi-episode crewmen and women who have never been seen before and are never seen again. In fact, he's treated as if he's in the episode as if he has been there for quite some time. There's no reason why Chekov couldn't have been on the ship during the events of "Space Seed" and there's no line of dialog anywhere to contradict the idea that he might have been. If we're relying on SEEING Chekov in "Space Seed" to believe that he was there, then why aren't we insisting that Kirk have a picture of Carol Marcus or one of a young David in order to believe that THEY existed during the events of "Space Seed"? The movie tells us that Kirk had a child out of wedlock with Carol Marcus and that she's a brilliant scientist, and that Kirk took the Kobayashi Maru Test but Spock did not, it tells us that Khan's wife has died, that Seti Alpha IV exploded, that Genesis is a project that has been going on for some time, that the Enterprise has been made into a training vessel, that Spock is now a Captain, and it tells us that Chekov was on the Enterprise when Khan was there and that they met. We don't see any of this, but there's no reason why any of it can't be 'true'. If we accept any of this, then we must just accept all of it. Because there's no reason not to.
In fiction, a plot hole, a discrepancy, or an anomaly exists because of some prior rule of the fictional or real universe that precludes its existence or occurrence. Something that happens off-screen is not patently a plot hole, so long as it doesn't violate the laws, norms, or history the fictional universe you're observing. There is literally no reason why Chekov couldn't have been on the ship during the events of "Space Seed" and therefore no reason to disbelieve that he and Khan might have encountered each other during any one of the unseen moments in which Khan was on the Enterprise.