I'm currently currently reading Alvin Plantinga's Knowledge and Christian Belief (a leaner and simplified version of his Warranted Christian Belief) and the relation between evidence, justification (or "warrant" in his terminology), knowledge, and faith is exactly what he discusses. I'll provide an answer based on my understanding of what he says, since it seems plausible to me and relevant to your question. Everything I say should be implicitly qualified with "in my understanding". I will probably come back to this answer to modify and extend it as I get further along in Plantinga's book.
In the first paragraph I mentioned that "warrant" is Plantinga's term for justification. More precisely, he defines warrant to be exactly that which is added to true beliefs, to make them knowledge. We know sometimes we get lucky and hold beliefs that happen to be true, but unless the belief is held for the right sorts of reasons or due to the right sorts of processes, it wouldn't be right to call such beliefs "knowledge". For example, if I believe that I will come into some money tomorrow on the basis of a psychic's testimony, or because of a dream that I had where I won some money, or because of my astrological sign, can I really call the belief "knowledge", even if it turns out to be true? It doesn't seem so. In each case, there is something "wrong" with how or why I held the belief.
First, Plantinga attacks internalist (more specifically evidentialist) accounts of warrant. Internalism holds that whatever makes a belief warranted is internally accessible to us. We can think really hard about a belief and eventually figure out what makes it warranted because it's self evident, incorrigible, supported by other beliefs that are warranted, etc. Plantinga instead puts forward his account of warrant called proper functionalism. Proper functionalism places emphasis on how beliefs are formed. Roughly, if a belief is: 1. formed by properly functioning cognitive faculties; 2. formed in a conducive environment that such faculties are "meant" to function in; 3. such faculties are aimed at the production of true beliefs (as opposed to faculties aimed at wish fulfillment, providing comfort, or other facilities that do something other than produce true beliefs); and 4. moreover aimed successfully at true beliefs, then the belief has warrant. A belief that is both warranted and true, is knowledge.
Examples of such cognitive faculties might be memory, perceptual faculties like vision, capacity to reason, and so on. The belief formation process is causal - I don't look at a table, reflect on what I see, and on the basis of that together with some other beliefs about the reliability of my vision, conclude that there is a table. Rather my vision and other cognitive faculties directly and quite involuntarily cause my belief that there is a table. Vision, we assume, is typically a faculty aimed successfully at the production of true beliefs. And if in fact my vision is functioning properly and I'm in the correct kind of environment for my vision and other belief forming faculties to function (as opposed to when I'm dreaming or if I am a brain in a vat) then my belief has warrant. The key thing here is, as long as those 4 conditions are satisfied, the belief has warrant even if we don't know that the conditions are satisfied. In this way, proper functionalism is an externalist theory of warrant - what makes a belief warranted may not be internally accessible to those who believe it. This has the handy feature of "solving" problems of skepticism that trouble internalist epistemologies, since I could know that I am not a brain in a vat if these four conditions are satisfied, even if I don't know that they are satisfied (and hence I might not know that I know that I'm not a brain in a vat, even though I know that I'm not a brain in a vat).
Plantinga then puts forward models where theistic belief generally, and Christian specifically, could have warrant. He describes us as having a cognitive faculty, a sensus divinitatis ("sense of divinity"), that causes us to form in various circumstances beliefs about God. We might be watching a beautiful sunset, contemplating the vastness of the universe, happen upon a frozen waterfall (like Francis Collins), and the sensus divinitatis involuntarily (and seemingly irrationally or at least non-rationally, to evidentialists) causes us to form beliefs about God and his nature. It's not surprising after all, that if there is a personal God who is roughly the way that monotheistic religions describe him (offering us a direct and personal relationship), that he should implant within us a way to know things about him directly. Why should God expect us all to hold philosophy or theology degrees first before we can come to know things about him? Since such beliefs in God are formed non-inferentially, we say they are "basic" beliefs. We also need to be in the right environment - we don't peoperly form a belief that there is a table in front of us, if there's no table in front of us. Likewise, not any experience might cause us to believe things about God in all of us; it has to be the right kind of experience in the right environment.
As for faith, Plantinga describes a similar type of situation. Faith, on his model, is not contrasted with knowledge, but is a special kind of knowledge. Faith is God causing belief in us, for example in the correctness of some verses in the Bible while reading that passage. Phenomenologically, from the inside, this would feel like a spontaneously acquired conviction in the truth of those verses (perhaps in this sense it "feels like" faith - a strong conviction formed on the basis of something other than evidence). But if indeed the model described by Plantinga is true and the causal process of how the belief is formed is through the instigation of God on our properly functioning cognitive faculties, then the spontaneously acquired belief would in fact be warranted (if all four conditions of warrant are met), and if it were also true, would count as knowledge.
What's important to emphasize here, is that he is not arguing that his model of the sensus divinitatis and faith is correct (though he believes it is), but that if it's correct then the beliefs formed in such ways are warranted - there is a direct connection with the truth of the model and the warrant of belief. Parody objections that try to claim that belief in unicorns can also be warranted and basic would need to offer a model where the truth of the model (the existence of unicorns) can account for the warrant of the belief (a sensus unicornus installed psychically by the unicorns, perhaps? Though such things seem clearly absurd to me). If Plantinga's model is correct, then Christian belief has warrant, so there's a close connection between its truth and its epistemology. Objectors who challenge the warrant of Christian belief are therefore by implication challenging its truth, and would need to provide arguments that its false, over and above epistemological considerations.
Hopefully the above might be an answer to your question: "Ultimately, what is the relationship between evidence, faith, and knowing?" It seems more complicated than faith and evidence being at odds, at opposite ends of the belief spectrum.
If Plantinga is correct, then it seems that the emphasis on evidence might be misplaced. We rightfully believe all sorts of things, like (to use some of his examples) that there is a past and that the world didn't come into existence five minutes ago, or that there are other minds, without evidence. That's not to say we couldn't produce evidence for such beliefs if it were demanded of us (though less philosophically inclined folks might indeed be unable to produce such evidence). But that's not why we believe these things. We believe such things non-inferentially, or basically. If the faculties that produce such beliefs satisfy the conditions of warrant, that might be enough for these things to be knowledge. So, when you ask: "My intuitive notion of faith is that it is to believe something without needing evidence or proof; is this incorrect?" This seems correct to me, but even though something like faith might lack evidence, it could still count as knowledge (as long it's true and the four conditions of warrant are satisfied, even if we don't know it).
