Does inexperience teaching totally defeat one's chances of admission to an education program?
I have direct experience in your situation: I entered a MEd teaching program at a top-5 U.S. university with zero teaching experience. I did have five years of military experience, and I emphasized the leadership skills I gained from that, as well as the personnel management skills I learned. My college grades were mediocre (3.2 GPA in Electrical Engineering), GRE scores were decent but not phenomenal, and I entered the program to be certified in high school physics.
Is there any way to convince them to see past the inexperience? How does one overcome this?
You are in the enviable position of wanting to teach math, and STEM teachers are highly sought-after and needed right now. That isn't to say that you won't be competing against highly-competitive peers, but for what it's worth you will probably be competing against fewer peers.
To overcome the lack of teaching on your resume, you should highlight any experiences you have had working with students or children (e.g., did you TA a class? Were you a camp counselor? Think outside the box to find something relevant, but don't stretch it too thin -- e.g., lifeguarding probably wouldn't quite fit the bill, but mentoring junior acolytes at your church might). You should certainly discuss why you enjoyed the tutoring, and how that informed your decision to pursue a teaching career.
Furthermore, you need to demonstrate your passion for teaching -- talk about the middle school algebra teacher who opened your eyes to the beauty of mathematics, or the calculus teacher who gave you the first real taste of a formal proof. Talk about why you love mathematics, and how important you think it is for upcoming generations to get quality mathematics teaching.
The admissions committee needs to see something special in your application that will make you a great teacher, and personal experience means a lot -- do you have 26 cousins that flock around you during family reunions to hear stories (you're a great story teller! This is a fantastic skill for a teacher!). Did you wake up every morning in tenth grade salivating at the thought of fifth period trigonometry class? (you've got legitimate passion! [and may be the only person in the world who loved trig at that age...]).
MEd programs are one of the few programs where I believe a well-written personal statement can truly make a difference in your application, so make it good. Have one or more people read your statement and give good criticism. Write it one week and re-read it a week or two later, and edit it if you don't see the passion coming out. Ask your reviewers to look for passion (or, rather, ask them after they've read it what they thought, and if "passion" doesn't show up in any reviews, re-write it).
Your letters of recommendation are extremely important, as well. You should make sure your letter writers know that you are applying to teaching programs (not research programs), and that's what you would like them to focus on. You don't want a letter that says, "X is a brilliant mathematician who can focus intently on minute details of complicated mathematical proofs for hours at a time. He has the potential to produce award-winning mathematics." What you want is something along the lines of, "X was one of my most passionate students, who has a knack for coming up with succinct, meaningful explanations for complicated mathematical topics. I routinely saw him during office hours where we had enlightening discussions about the course. I learned as much from him as he did from my own teaching."
Your interview is obviously important, too. I suggest preparing something to teach for five minutes (high school level--if I were preparing something, I might choose compound interest -- you can teach it in about five minutes to a willing audience, and you end up with the beautiful definition of
e in the end), and practicing it on someone. If I were interviewing candidates, I'd ask them to teach me something (maybe something particular), and if you have something in your back pocket that you've practiced, you'll be ready for the question if it appears. Be prepared to discuss why you didn't have the opportunity to teach (what did you do during your summers? Were there TA opportunities that you could have taken?). Obviously, do a lot of smiling and be as personable as you can without going outside your normal personality. Have a very succinct answer to why you believe you will be a great teacher -- 30 seconds that will wow an interviewer. (one further tip: if you have an interview with multiple people, remember their names and address them with their names during the interview--this can make a very good impression).