One is purchasing a month to month phone plan with cash for example

They could require you to show an ID to purchase a phone.

Or finding open wifi networks

Open wifi networks certainly wouldn’t provide an ID to connect, which would mean they couldn’t be used to access social media.

This is not an unsolvable problem. The question is if Australia is willing to piss everyone off to actually do it.