Apparently its ultimate origins are somewhat disputed, but the most likely source is the Greek kyriakon, meaning "of the Lord" (the Greek word for "Lord" being kyrie). This seems to fit in terms of phonology and semantics, but not necessarily in terms of history. The usual term in Latin was ecclesia, which also came from Greek and is the source of the words for "church" in all the Romance and Celtic languages.
So if the Germanic word for "church" really does come from Greek, it must have been borrowed in the first few centuries AD, because it was already in use by the Angles and Saxons when they invaded Britain. But the Germanic tribes at the time were still pagan, not Christian, so it was not spread by the structure of the early Christian Church.
They would have known what a Christian chuch was, though, because they were frequently in contact with the Roman Empire and often looted churches, so it's not surprising that they would have had a word for it.
The generification of the word is not a recent phenomenon, though. It was used to refer to non-Christian church buildings and to the Christian community from about 800 or 900 AD. It looks like it's been used to refer to non-Christian religious organiations for only a couple hundred years, though.