Will lack of teaching experience be a major hindrance for a faculty position? I'm currently a post doc (in theoretical computer science) and the only teaching experience I had so far was to teach some tutorial classes for undergraduate courses and giving some "guest lectures" in some graduate classes. It seems that most positions for assistant professor require you to show some teaching experience, i.e. at least co-teaching some courses. The problem is, my current department is quite inflexible giving such assignments to postdocs. 

On the positive side, I got some pretty good student evaluations for the tutorials I've been teaching, whether that is considered helpful without teaching a "real" course, is of course a different matter.

Overall, my research record (several tier-1 publications) beats my teaching record (by far). 

Will my lack of teaching experience be a showstopper when applying for follow up positions?
I'm surprised to hear you say that "most positions for assistant professor require you to show some teaching experience, i.e., at least co-teaching some courses."  If you are applying to positions in the U.S. where research will be your primary duty, your prior tutorial and guest lecture experience should be sufficient to get you past whatever minimum you need, especially if you have evaluations to back this up.  Of the five colleagues of mine who received tenure-track offers at Reasearch I universities, only one of them had co-taught a class, and the others had one semester of TA experience which was, primarily, grading.

That said, there are other ideas for getting teaching experience:


Creating your own course or seminar to teach in the summer or during a January term.  If you pitch it as a non-credit course, it might be easier to convince your department to let you teach it.
Look for adjunct work at a local community college.  You'll probably be limited to introductory courses, but this gets you experience.  You may need the buy-in from your faculty boss at your current school.
Talking to individual professors about helping with their course -- I find it hard to believe that everyone has all the help they might like already, and you may have more luck getting your foot into a classroom without trying to be officially assigned to it.