The Church (which in concrete terms means the Pope, and in this case Pope Innocent III) might have been able to overthrow John and arguably came close to making the attempt. By 1204, John had lost most of his French lands, including the Duchy of Normandy, to King Philip II of France, operating under the aegis of the Pope. This resulted in the collapse of the Angevin Empire and a strong shift in the balance of power in Europe towards the King of France. When the dispute over the succession of the Archbishop of Canterbury was raging, after the papal interdict of 1208, it appeared that the Pope might attempt to oust John as King of England as well.
Instead, John submitted to Pope Innocent III, in terms formalized by the Bulla Aurea in 1213. From this point on, the Pope was technically (at least from the perspective of the Church) the ruler of England, with John as his viceroy. This seems like a huge defeat for John, but in fact, he gained considerably from the arrangement. The common people knew nothing of the technicalities of the agreement, and everyday matters continued in England exactly as they had before. However, after 1213, the Pope considered John as his loyal servant and backed whatever he did. This is why the barons, who eventually forced John to sign the Magna Carta in 1215, received no assistance when they attempted to appeal to the Pope.