First of all, don't think too hard about time travel in Star Trek; it's not any less convoluted or better explained that in any other fictional work.
Obviously, the presence of Kirk, Spock and McCoy in the past would have changed the timeline, regardless of the outcome of that episode. People would remember them having been there, their actions would rippled out from there, etc. So, it's not surprising that some details about Keeler's death were different.
However, the major event of her dying was the thing that needed to happen either way. We don't get any details about the car accident to know what she was doing crossing the street. Presumably, without Kirk in the picture, there would have been other people she was friendly with, possibly even someone else she was going to the movies with. There's any number of reasons she might have been crossing the street at that time.
Another possible explanation is that there was only ever one timeline: the one in which Kirk went back in time and ultimately caused Keeler's death. Everything else that happened in the episode was merely the events of that original timeline playing out, including the temporary "glitch" where McCoy changed things.
This doesn't make much sense if you think of time linearly, but note that this episode was largely written by Harlan Ellison, who has written a number of high quality time-travel stories (and was a big fan of Doctor Who). It's possible, even likely, that Ellison put this paradox into the episode on purpose, to demonstrate the complexities of time travel and force the viewer to draw their own conclusions as to what really happened.