Is it possible to teach without a PhD?

Typically at larger "more prestigious" institutions, Professors must have their PhD to teach. It has been my experience that some smaller institutions will allow MS holders to teach undergraduate students - but your mileage may vary.

As an example, a friend of mine has currently taken over a Computer Science department at a small institution and only has his Masters. While they would prefer a PhD holder, they can not find one to take the job.

So, technically, yes - it is possible. Although you may not find yourself at a top-level institution.

Yes, absolutely, it is possible, at least, here in the US. Lots of top schools use teaching faculty for large undergraduate courses, especially in computer science and engineering and a few of them (like me at Michigan) only have a master's.

The rule is you're supposed to have one degree higher than the students you're teaching or a terminal degree, i.e., a PhD. So, if you're only teaching students working on their bachelor's, all you really need is a master's. Even if their post says applicants should have a PhD, it doesn't mean you can't get the job without one. (What else do you bring to the table?)

What matters is whether you can teach. So, the search committee will be looking for teaching experience and ability. The way to get the experience when you have none is (or was for me) as a part-time affiliate or adjunct instructor, perhaps starting out teaching a lab, later a lecture course. (Part-time opportunities tend to open up last minute when they realize they've got a hole in their schedule, a course they've promised to offer but no one available to teach it, and they're desperate to find someone right away. This is especially true of summer offerings. Check in regularly with the chairs or whoever's doing scheduling at the relevant local departments to let them know you're available.)

The search committee will ask for your CV, some LORs, a few short essays, e.g., describing your teaching philosophy, list of classes taught, probably want to see past student evals, and perhaps a short video of one of your classes. If they like what they see, they'll ask for a teaching demonstration where you'll present a sample lecture and they will role-play as students. (Hint: Never take new material on the road. If you're asked to give a teaching demo, give a lecture you've previously given and thoroughly debugged in front of a live class, hopefully several times. Pick something where you know you nailed it. The quality of your lecture is far more important than the topic, so don't try to "pitch" your lecture to what you think the department is looking for with new untried material.)

Teaching appointments are not tenure track positions, it's all teaching, no research, and the pay and status is lower, which is why they're not very attractive to top PhDs. So, it's a lot harder to attract really good teaching faculty than you'd think and why they may be willing to hire you with only a master's if you can do the job. Typical contracts are initially 3 years, then 5 years at each renewal. At many schools, the title is some variation of "lecturer". That's what we have here at Michigan, where it's Lecturer I through Lecturer IV. (Yeah, no one likes the title.) Some schools have switched to a variation on "teaching professor". University of Washington now has Assistant Teaching Professor, Associate Teaching Professor and Teaching Professor titles.