Sorry, but I have to agree with the skeptics. Vinland would have been generally superior to Australia regarding Norse living conditions and was closer, but the Norse still didn't manage to settle it permanently. While it might have been possible for a very bold explorer on a single ship to reach Australia, that isn't nearly enough for a permanent colony. You need not only consistent travel to get enough men and women for a genetically viable population without being subsumed by the aboriginals, but you'd also need easy enough travel for viable trade just to make it attractive enough for the vikings and to maintain cultural exchange to keep it Norse.
I see only one real possibility. Vinland succeeds for whatever reason. We'll say Erik the Red was blown off course, settled Vinland instead of Greenland. Then King Olaf's crusade to Christianize Norway by the sword starts a mass migration of all the remaining pagans to Winland as Erik the Red sent his sons to talk all about it in hopes of drawing colonists. The challenge of keeping contact between Vinland and Europe forces an improvement in naval technology. With improve naval technology, two paths open up.
1) The Norse focus on trading as their ability to conquer starts failing, their naval capabilities and culture giving them an advantage. Maybe they take the Canary Islands, Cape Verde, etc, to control the african ivory trade that strangled Greenland's economic viability. They eventually reach South Africa, and decide to try and undercut the spice trade that the Middle East controlled through the Silk Road and the Red Sea-India trade route. They might thus reach the point where they could reach Australia and might even view it as a decent place to put a colony since taking a chunk of India or Indonesia might be more difficult.
2)The other option is that as the Viking Age in Europe winds down, the vikings, or at least Norway, decide to focus on taking Vinland by the axe. They settle the coast gradually southwards, relying on their naval capabilities over venturing inland. Eventually they control the western coast of the America's all the way down to Pantagonia. By that point they might have the naval capabilities to cross the Pacific Ocean west to Australia. Although New Zealand would probably be the more attractive proposition.
Now obviously these two possibilities are very much a stretch, and rely on POD's either early in the Viking Age or a Vinland POD. Even then, you're talking about hundreds of years of development without the other European, Africa, or Middle East powers trying to put a stop to it or the vikings successfully beating them off. Unlikely. Even then, I really don't see anything less than 250 years being enough for them to spread far enough for it. Probably closer to 400. So 250-400 years after your POD. By that point its less a story about 'vikings settling Austrialia' and more 'vikings expand across the world to the point that they settle even Australia.' It'd be a viking/Norse wank by then.
So, yeah. Unless you literally make it ASB like having a portal appear that leads from Scandinavia to Austrialia or having a great population be teleported to Australia, not really going to happen. Australia is basically as outside the sphere of viking influence as anywhere in the world. If the vikings went southeast, they'd likely focus on Africa and they'd be dealing with the vast amounts of peoples and cultures of Central Asia/Middle East. If they went southwest, both North and South America would be more opportune targets for colonization.
I see only one real possibility. Vinland succeeds for whatever reason. We'll say Erik the Red was blown off course, settled Vinland instead of Greenland. Then King Olaf's crusade to Christianize Norway by the sword starts a mass migration of all the remaining pagans to Winland as Erik the Red sent his sons to talk all about it in hopes of drawing colonists. The challenge of keeping contact between Vinland and Europe forces an improvement in naval technology. With improve naval technology, two paths open up.
1) The Norse focus on trading as their ability to conquer starts failing, their naval capabilities and culture giving them an advantage. Maybe they take the Canary Islands, Cape Verde, etc, to control the african ivory trade that strangled Greenland's economic viability. They eventually reach South Africa, and decide to try and undercut the spice trade that the Middle East controlled through the Silk Road and the Red Sea-India trade route. They might thus reach the point where they could reach Australia and might even view it as a decent place to put a colony since taking a chunk of India or Indonesia might be more difficult.
2)The other option is that as the Viking Age in Europe winds down, the vikings, or at least Norway, decide to focus on taking Vinland by the axe. They settle the coast gradually southwards, relying on their naval capabilities over venturing inland. Eventually they control the western coast of the America's all the way down to Pantagonia. By that point they might have the naval capabilities to cross the Pacific Ocean west to Australia. Although New Zealand would probably be the more attractive proposition.
Now obviously these two possibilities are very much a stretch, and rely on POD's either early in the Viking Age or a Vinland POD. Even then, you're talking about hundreds of years of development without the other European, Africa, or Middle East powers trying to put a stop to it or the vikings successfully beating them off. Unlikely. Even then, I really don't see anything less than 250 years being enough for them to spread far enough for it. Probably closer to 400. So 250-400 years after your POD. By that point its less a story about 'vikings settling Austrialia' and more 'vikings expand across the world to the point that they settle even Australia.' It'd be a viking/Norse wank by then.
So, yeah. Unless you literally make it ASB like having a portal appear that leads from Scandinavia to Austrialia or having a great population be teleported to Australia, not really going to happen. Australia is basically as outside the sphere of viking influence as anywhere in the world. If the vikings went southeast, they'd likely focus on Africa and they'd be dealing with the vast amounts of peoples and cultures of Central Asia/Middle East. If they went southwest, both North and South America would be more opportune targets for colonization.