Some states in Australia offer vocational entry, where you are trained on the job and paid (NSW does, I can't remember the rest off the top of my head). Many places are limiting the number of people accepted and are phasing out these programs however.
CSU, ACU and WSU offer courses in NSW, other unis in other states do as well. I'm currently at CSU, B. of Clinical Practise (Paramedics) is a 3yr degree at Bathurst or Port Macquarie. Certain people can do it via distance ed, however its only if you're a current paramedic or army medic I think. CSU also does a grad dip to become a paramedic that you can do if you have a nursing qualification/background