In the US, rules are not so strict. In 2007-08, 71.6 percent of secondary math teachers had been math majors. An additional 16.2 percent were certified in math but did not do a math major. 12.2 percent of secondary math teachers had neither a major nor a certification in math [1]. The number of uncertified non-math-major math teachers is much higher in lower grades, as you point out.
>Your elementary teacher may not be a math major
In general they won't be, and I wouldn't expect them to be. The subject matter of these classes is usually much simpler than freshman calculus.
It's not math per se that I care about here. If, for example, these future elementary teachers disliked reading and displayed the same attitude towards being asked to write critically about a novel, then I would consider that equally disqualifying.
Your elementary teacher may not be a math major because they are expected to teach all subjects. There is also probably some bias against deep content knowledge because "it's elementary school after all".
Secondary Education degrees are subject specific, so secondary education math students would, in fact, be mathematics majors.