Hi
In regards to Australia, it would depend on your discipline. I'm in social sciences, and yep, people don't need to have a Masters, but it does help. Otherwise you'd need to have a good undergrad degree with first class honours. I don't think there's a site like findaphd, but I didn't need to search for mine - I contacted a potential supervisor with an idea for a topic, and went from there.
Here's a site that might help: http://www.studyinaustralia.gov.au
Good luck!