It's also possible that Khan met Chekov shortly after the events of "Space Seed," but before Khan's people were dumped on Ceti Alpha V. In To Reign in Hell, I made a point of establishing that Chekov was among the crew members who escorted Khan and his people to the planet and provided them with supplies, said goodbye to Marla, etc.
The simplest explanation has always been that Chekov was already a member of the crew during Khan's takeover, just not assigned to the bridge yet.
IIRC, Vonda McIntyre suggested a friendship between McGivers and Chekov in her novelization.
Yep, and I borrowed that for To Reign in Hell, where Chekov is the last person to say goodbye to Marla, whom he'd always had a bit of a crush on . . . .