I think the old Kirk and Spock have to be there, in the 1930's... and here's why:
Time travel has to always work the same way. In "City on the Edge of Forever" Kirk and Spock did change time, they created a new alternate reality. It just wasn't *very* alternate. When they went forward again, everything looked more or less the same.
The old Spock in the movie comes from this new timeline. When he goes back, the establishing moment of the timeline - Bone's encounter with Edith Keeler - has to still be there.
Look at it this way: what a year after the events of the movie, new Kirk goes back in time a year, to the middle of the film. While there, he changes things so that Vulcan doesn't get blown up. So, now we have yet another timeline. But this new reality still has old Spock from TOS in it. Otherwise it just doesn't make the slightest bit of sense. He can't go back and suddenly find himself in the TOS past, where his father never died. That reality is inaccessible, just like the 1930's without Kirk and Spock now is.
And yes, this pretty much means we should see time travelers from hundreds of alternate futures around. Which is actually kind of like the X-Men comics, when you think about it.