In the beginning of Terminator: Genisys, John Connor saves Kyle Reese when he was a child. How does that fit to the plot of the previous movie, where Kyle Reese is 16 years old and has never met John Connor?
It doesn't fit, and there was no intention that it should fit.
Regarding Kyle Reese being 16 and never having met John Connor before that age, you are referencing Terminator: Salvation.
The writers of Terminator: Genisys, Laeta Kalogridis and Patrick Lussier, had received advice from Terminator creator James Cameron by way of producer David Ellison, giving them permission to largely ignore both Terminator 3: Rise of the Machines and Terminator: Salvation, as these films are not well-regarded by fans nor by Cameron himself.
...production of another installment [Genisys] in the series was set up in collaboration with Skydance Productions, owned by ... David Ellison. The Ellisons made sure to ask for the input of Terminator creator James Cameron, hoping to create something that would get closer to the spirit of the original film and sequel Terminator 2: Judgment Day.
In effect, Cameron has distanced himself from the third and fourth films, calling Genisys the real "third film". Therefore, Rise and the Machines and Salvation have become a different canon from The Terminator, Terminator 2, and Terminator: Genisys, and continuity between Salvation and Genisys was not imposed.
Following a screening of Terminator: Genisys, franchise creator James Cameron essentially told fans that they could ignore Terminator 3: Rise of the Machines and Terminator: Salvation when they go to see Terminator: Genisys, saying "in my mind I think of [Genisys] as the third film."
Cameron has previously revealed that he's not a big fan of either Rise of the Machines or Salvation. On the other hand, having seen an early screening of Genisys, he seemed to approve of the Alan Taylor directed sequel.
"It's being very respectful of the first two films," he says, "and then all of a sudden it swerves and now I’m going on a journey."
The upshot of all this is that the two Kyle Reese back stories are elements of different canons. Cameron tells you to ignore the Salvation one in favour of the Genisys one...
Like someone said, the two meetings happen in two different timelines, or "universes". So both can be considered canon.
The future scenes in Terminator: Genisys are supposed to happen in the original timeline, or at least, the timeline that follows only the first film. In this timeline, Judgement Day happened in 1997.
But Terminator: Salvation takes place in the timeline that was altered when Cyberdine was destroyed in Terminator 2: Judgement Day, and is the same continuity of Terminator 3: Rise of the Machines. In this timeline, Judgement Day happened in 2004 (as shown in the third film), not 1997.
So, in a nutshell, both scenes depicting the meeting of John and Kyle simply happen in two parallel timelines.