Was it ever stated on screen when the 5 year mission began? It seemed that in Where No Man has gone before Kirk and Spock had a good friendship and seemed they had been serving together a long time.
Could WNMHGB be late in that first year? middle of the second? that would synch up with the new timeline a little better created in Trek XI.
In the confines of TOS itself, no. Within TOS, taken by itself, there are contradictory references as to when TOS takes place. Much of canonical references to the "dating" of TOS were superimposed over the TREK franchise by subsequent movies and series.
Having said all that, these superimposed references, (which are not necessarily consistent, either) have over the years established "Where No Man..." as having taken place in 2265 and the Enterprise's famous five-year-mission as having ended in 2270. Since "Where No Man..." was filmed in 1965, it would seem that the (roughly) implied "official" position of Paramount (again, having slowly and gracelessly evolved over the years) that a given TOS ep would be (roughly) set some 300 years after it was filmed in Hollywood. So if an ep was produced in 1967, it can be assumed to be set in (roughly) 2267.
The logic behind this is far from perfect, to be sure. But it does "work" if you don't take it too literally.
As for whether "Where No Man..." is technically part of the "five year mission", well, that depends on how literally you drink the Paramount Kool-Aid. It was never made clear what was meant by a "five year mission" to begin with. What does it mean? What does it entail? One could extrapolate either way. Was the Enterprise modified/refit after returning from Delta Vega, thus suggesting this to be the point at which the five year clock started ticking? Or did the five year clock start when Kirk took command from Pike, presumably some time before the ship received orders to leave the Galaxy? You can make arguments either way.
Consider this: Capt. Kirk was ordered to take the Enterprise on a deep, deep space probe into a supposedly dangerous extragalactic area. The Enterprise discovers what's left of the S.S. Valiant, and it's not clear if that's what Kirk was sent there to find or if this discovery was a surprise. After clashing with the Barrier, the Enterprise is crippled and suffers casualties. The dialogue in the story suggests the ship's crew is able to effect repairs while at Delta Vega and then returns to the nearest home port,
however, it is not
explicitly spelled out that this is what happened. Did the Enterprise return to starbase, or did Kirk go back out to probe again before going home?
Could "Where No Man..." have been an aborted mission by itself? When the barrier was (supposedly) documented by a Federation starship for the first time, perhaps that mission was scrubbed and the Enterprise was subsequently recalled, refit, recrewed and reassigned with an entirely different (five year) mission.
You could make an equally persuasive argument that Starfleet sent Kirk and company to investigate some garbled signal, after having previously sent out probes into that area, and maybe Kirk had some idea what he would find there. So maybe Starfleet had suspicions about what was "out there" beyond Delta Vega, and the Enterprise was sent there for a limited short-term mission before returning to home base for refit before starting the new mission.
We don't really know.
We
assume that Enterprise returned to home base immediately after Delta Vega, then was refit under Kirk and Scotty's direct supervision, and then TOS began some time after launch. You can therefore make the argument that the five year clock did not start ticking until
after that launch.
When it comes to Kirk knowing Spock and/or Mitchell prior to their extragalactic voyage, it is entirely possible these men served together before the probe. Where they may have served together and in what capacity was never made clear. Spock said he served with Pike for over 11 years. And Kirk told Mendez he met Pike for the first time "when he was promoted to Fleet Captain. I took over command of the Enterprise from him." Depending on how you take this, Kirk could have briefly served as Pike's XO (or as a junior captain in a flotilla under Pike's flag) before assuming permanent command of the Enterprise. Again, depending on how you take the most recent movie, we still don't know.