That's only if you are speaking of protection without procedure to allow the employee to improve or checking to see if there is a medical reason (including mental health issues). Otherwise, no. This simply isn't true. You can still let employees go because they aren't actually doing their job, just like you can still let employees go for bad attendance, among other things. Unsurprisingly, the call center I worked at had high turnover (both employees quitting and getting fired) before and after it became unionized. But it does make it harder for employers to use these excuses willy-nilly.
"Could be killed by a union".. yes, or they could be killed by corporate policy or management that lets rules slide for employees they like.
Your example of teachers unions is a bad one, as they often get villified. Yet, we know there are multiple reasons for a so-called "underperforming" teacher, multiple solutions that help, and the fact that one has to be able to replace the teacher if you let them go, all complicating the issue.
"Pay may be solely based on tenture, not skill"
Note your use of "may be". Tenure-only pay is often used for jobs that you can't measure the skill of one person against another: Factory jobs, for example. These often still have a pay range, giving more for folks with education than those without, for example. What changes is generally transparency: Skill measures and the evaluation of those skills needs to be communicated to employees in ways they can meet and/or improve them. In addition, these same issues happen outside of unions as well.