Teach the math teachers how to code, and they become your CS teachers. This is more or less how my HS got enough teachers to teach the CS courses, as they made it mandatory for all students to learn.
Learning how to code is easy; a lot of teachers can do it. Learning how to debug is quite a bit harder. Learning how to debug someone else's code is a lot harder. But this is essential in being able to teach coding effectively (not debugging someone else's code as such, but being able to find the bug and steer the student into a way of finding it themselves).
Your proposition also assumes that you have enough Maths teachers, which Australia is certainly lacking (for the same reasons as OP)
This is also how my high school did it. It didn't work out well, although as far as I know they're still teaching. These weren't bad math teachers: they were probably some of the best in the school; it's just that the couple months or a year of training they must have received was clearly not enough for them to handle those classes at all.
