I've been in Australia for over 2 years, coming in under the 457 program. No degree either, and it didn't seem to be a problem. Getting PR through a 457 is pretty straightforward, though it will take 2 years and is more expensive now than it used to be. The upside is there's no skills test going this route.