there's not that much information about contemporaries; we're not talking about a written culture here. (In Rome maybe, not in the provinces). As I think jake once pointed out, Jesus himself is only said to have written one thing, with a stick in the sand.
One non-written piece of evidence: the Holy Sepulchre. This has been a site of pilgrimage since the earliest times - the days of people who knew perfectly well where the crucifixion took place because they were there. Hadrian had it concreted over and a statue of Jupiter erected - which of course helped Christians find it and dig it up again when the empire became Christian. It's housed a church more or less non-stop ever since.
My guess is that Jesus existed because, as I've said, what would be the point of inventing him? If people were really in it for the money or the glory, they'd have been better off claiming to be the saviour themselves. His teachings in the Bible seem pretty coherent - though how far they reflect what he actually said at the time, and how far they've been edited into coherence, we'll never know.