Solution: Skynet shouldn't know about him to begin with. Easy as pie. No time-paradoxes to worry about.
Though if you want to get technical, before T3 came out, the end of T2 was a huge paradox: If John and Sarah had really prevented the war, how could John have been born?