John Connor should never have been born as he is only born when he goes back in time.
Yet in order to go back in time, John Connor must have been born...
Which can't happen unless he goes back in time.
You are close but John Connor does not go back in time - Kyle Reese does.
It seems paradoxical that John Connor would exist without having sent his dad back in time to impregnate his mom. Presuming only Kyle Reese could be his father, then someone other than (or a different kind of) John Connor must have sent him back.
How does John Connor exist if his father was born after he was? Prior to sending Kyle Reese back in time, who was John Connor's father? If it was someone other than Reese, wouldn't - at the very least - this give John Connor a different set of genetics?
The "paradox" presumes - as Steve-O points out, like the grandfather paradox - that only Kyle Reese can be John Connor's father. Possibly someone else was initially John Connor's father and Kyle Reese getting sent back in time changed the events. Possibly the father is irrelevant and it is simply being the son of Sarah Connor which determines how John comes to lead the resistance?
Then there is the question of timelines and how the future of Connor sending Reese back in time relates to the altered past of Reese fathering Connor. Does this altered past shown in "The Terminator" (1984) simply diverge and become a new (space)timeline altogether? Or, if there is only one spacetimeline and, like in "Back To The Future", do the changes to the past immediately effect the future? What kind of gets lost in this narrative conceit is the question of "where/when is the present?" In "The Terminator" the "present" seems to be the future's past which is what the audience is watching and we don't know if changing the past affects the future, or has created a divergent timeline.
Fortunately, movies don't really need to make sense or answer fundamental questions about physics to be enjoyable. When considering time travel, though, keep in mind the idea of spacetime. If I went back in time a minute ago, would I still be in the same place? ooooOOOOOoooooo ;)