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.
Your proposition also assumes that you have enough Maths teachers, which Australia is certainly lacking (for the same reasons as OP)