Could "Naše strana má nového předseda." also be accepted? Duolingo marks it as a typo but I thought that masculine nouns always changed their ending to -a in the 4° case.
No, it is not correct. The accusatives of the masculine paradigms are: pána, hrad, muže, stroj, předsedu, soudce. As you can see, there is no universal ending.