In the very earliest Church there were two chief schools of interpretation, coming out of two different catechetical centers: Alexandria and Antioch. The Alexandrian school, of which Origen is perhaps the examplar, favored allegorical interpretation. The Antiochene school, of which Theodore of Mopsuestia is perhaps the highest achievement, favored a more literal interpretation.
Starting right here, though - back in the AD 200s - the word "literal" was not being used as we use it today. And its contrast was not its contrary. That is, it was generally understood that a thing could be understood both literally and allegorically. In fact, it was very common to discuss texts on both levels.
Traditionally, through the Church's history, literal interpretation has not meant "reading the text to mean just what it seems to me to mean." At least as far back as St. Augustine we see that this is so. Rather, the literal sense of scripture was contrasted with the spiritual sense. The literal sense is the meaning intended by the human authors at the time of writing, and the spiritual senses are the meanings embedded into the text by the Holy Spirit at that time and thereafter. In his The Literal Meaning of Genesis, he asserts theological reasons to believe that the world was created, together with all its component parts, simultaneously. He also make the case that the literal meaning of the Genesis creation accounts are figurative. See Wikipedia's summary of Augustine or an excerpt from The Literal Meaning of Genesis to see how early and how prominent a teacher of the Christian faith held this view.
How can the literal meaning be figurative, though? And moreover, when did people start thinking that a "literal meaning" was a "face value" reading, or "the text as it appears to me"? As to the first question, if we bear in mind that many writers often write figuratively to convey a meaning or moral, and that they do not always start by telling us that this is their endeavor, but rather, expect us to understand that fact, we can see how the same thing happened in antiquity. Nobody in modern times expects the story of the Three Little Pigs to be either (a) false or (b) literally about three talking pigs and the talking wolf who stalked them. Rather, we all know that it is about a moral, about doing things right the first time as a security against future adversity. Nobody needs to tell us that. Small children pick up on it because they know that pigs do not talk and that their parents, telling the story, are not fools who think that pigs talk.
As to the second question, I do not know that I can put an exact date when the shift in understanding about literal interpretation happened. It certainly happened after the medieval period because none of the medieval theologians interpreted Genesis as modern scholars might. In fact, if anything their vice was the contrary vice - they are accused by the Reformers of over-symbolizing every account and story. I suspect Luther's insistence on the ready interpretability of Scripture may have facilitated this shift. Certainly by the time of the fundamentalist revival of the early 20th century, the practice was well established in the Protestant world, and even earlier, since the Protestant liberal theologians of the mid-19th century reacted against the practice of interpreting scripture at face value, of asserting that the "plain meaning" of Scripture is what the scriptures plainly meant.
Having established the literal meaning, which we might also call the historical meaning - the meaning meant by the historical author - it becomes easier to see spiritual and allegorical senses and to judge their validity. If we confuse the senses, or the meaning of "literal sense" in the first place, our whole interpretation becomes hopeless convoluted.
Let's consider two cases.
First: the incident of Jesus rubbing mud on the eyes of a blind man in order to restore his sight. The literal sense in this case is that Jesus rubbed mud on the eyes of a blind man and thereby restored his sight, though he might have done so in a thousand ways. St. John seems to intend that Jesus actually did these things. Fine. I believe St. John. An allegorical sense might be added to this without at all contradicting the reality and truth and factuality of the first literal sense. St. John, or the Holy Spirit through St. John, might also wish to teach us something like, "God can use common, even grubby, stuff to bring about healing in our lives. Don't doubt him even if it looks like He's throwing mud in your face."
Now, the Antiochene school tended to look at the first sense and stop there; the Alexandrian school tended to neglect the likely intention of the author of the text and just apply symbolic meanings to everything.
Second case: Genesis creation account. Taken at "face value" so that we believe the author to intend what the words actually say, no more no less, the text poses contradictions (day before the sun) that any child would pick up on. Not a problem for the Church fathers like Augustine because they understood that "literal" does not mean "face value", but rather "what the author was trying to say." Getting bogged down in how many years does a "day" represent is totally aside from the point if that wasn't the author's point. If the author is trying to use seven days to show, say, seven strata of creation - from the most primordial (light and darkness) to the most intelligent (animals and humans) to the most sublime (resting with God) - well, then that allegory is the "literal meaning" in the Church father's understanding. Any spiritual interpretations have to be built off of that, rather than off of some other interpretation.
This understanding of "literal" means we might have to do a lot of research about what the authors meant (a task for biblicists, linguists, archeologists, historians, all of whom should love and cherish the Bible as the Word of God) - but it does save us the heartache of relativism. After all, if in one hundred years, people interpret the text as "literally meaning" something different than we think, who is to correct whom? In that case, it's all about our understanding of the text. As the Church fathers read it, though, it is about the author's understanding of the text.
In the case of the Genesis accounts of creation, it should be telling that not one of the Church fathers "took it literally," that is, thought it implied a seven 24-hour period of time, or anything like that. Nor, as far as I am aware, did any rabbis. They were closer to the original authors in time, place, and culture. This very simplistic approach to understanding a complex book is a very modern phenomenon - just in the last couple centuries, really.
