Specifically the Catholic Church and Orthodox Churches. Without wine and wheat, you cannot practice the religion. Were there substitutes allowed in some cases?
Ah, this was in fact the topic that attracted some attention from some of the top theologians in medieval Western Europe in the 13th century.
To give an example, Thomas Aquinas (d. 1274) argues in his famous Summa Theologica (the English translation cited below is taken from this online edition) that:
"Whether the matter of this sacrament is bread and wine? (III. q. 74)"
"(Hypothetical) Obj. 2: Further, this sacrament is to be celebrated in every place. But in many lands bread is not to be found, and in many places wine is not to be found. Therefore bread and wine are not a suitable matter for this sacrament".
"I answer that.....Fourth, as to the effect with regard to the whole Church, which is made up of many believers, just as bread is composed of many grains, and wine flows from many grapes, as the gloss observes on 1 Cor. 10:17: We being many are . . . one body, etc".
"Reply Obj. 2: Although wheat and wine are not produced in every country, yet they can easily be conveyed to every land, that is, as much as is needful for the use of this sacrament......."
Thus, Aquinas proposes two possible solutions to this question, namely 1) bread/ wines made of different grains and grapes are also permitted to use in the sacrament, and 2) the more intensifying trade will export these two necessities for the Catholic liturgy also to the places where they don't be grown by themselves.
On the other hand, similar inquiries from the peripheral part of the Latin Christendom had already annoyed the Pope. In 1237, Pope Gregory IX answers in the response to Archbishop Sigurd of Trondheim/ Nidaros on behalf of his bishops in the North Atlantic church provinces that only the bread made of grains ("panis de frumento") and wine made of grape ("vini de uvis") should be used in the sacrament (Diplomatarium Norvegicum, I-16). While the response of the Pope itself was rather curt, however, it is worth noting that the local suffragan bishops of the Norwegian archbishop had been worry about the possible consequence of their practice at first and formulated the question - The archbishop in turned collected these questions and submit to the Pope in Italy (the archbishop got several response to the local problem from the Pope in the same month). In other words, it was not the top-class theologians and the Pope himself, but also some local clergies either in Norway or in the North Atlantic Isles like Iceland also shared common awareness of this issue by the middle of the 13th century.
As I mention recently in: Modern Iceland is self-sufficient in dairy, meat, and eggs, but imports the vast majority of its other food, since the land is mostly not suitable for farming. Was the local diet mostly animal-based in the Viking age? What else were they eating?, the Norse settlers around 1200 had learned how to make the substitute of wine from local crowberry, the clergy in question had not apparently been fully convinced of it.
Were there substitutes allowed in some cases?
I suppose so, at least in a few exceptional cases. In 1308, Bishop Arne of Bergen, Norway, also sent a barrel of (probably dried) "wine berry" for the liturgical use (substitute wine made of dried grape) to his colleague, Bishop Þórðr of Garðar, Greenland (Diplomatarium Norvegicum, X-9).
Reference:
(Edited): fixes the format of Aquinas' argument.