How there could have been a tradition of the Church before there was a New Testament?

The evolution of Christianity was a complex process. Although one could argue that it began with Jesus and his followers, another way to think about Christianity as an organized religion is to date its foundation from the death of Jesus, when various of his followers needed some organized way to propagate his message. If you read the letters of St. Paul, which are now part of the New Testament, you can see that there were various Christian communities in existence before Paul began his mission. In fact, many of the letters and travels of Paul have as their purpose communicating with such communities which had been founded by various other disciples or traveling missionaries. 
These early converts and teachers relied on orally transmitted traditions, including stories and sayings, handed down orally from teacher to pupil and missionary to convert, many of whom may have been illiterate (note that literacy was restricted mainly to upper class men in this period). These Christian communities, who practiced baptism and celebrated the Eucharist, constituted the Church, and while they had many oral traditions and perhaps some written narratives or collections of the sayings of Jesus, their traditions existed long before the New Testament was assembled into its current form (a process that was not completed until the second century), and before the Gospels as we know them were written down. In fact, the four Gospels probably reflect four slightly different church traditions.