While i love The Pogues’ version of that song, it was actually written by the same guy that Telemark mentions here, Eric Bogle.
Then there’s the old kids’ song “Kookaburra”. We used to sing that in grade school (in New England!).
Here’s Eric Bogle singing - And the Band Played Waltzing Matilda. It’s been covered many, many times.
The Australian band Redgum have various songs that deal with aspects of Australian culture and history.
“I was only 19” deals with the Australian experience of the Vietnam War.
I’ve been To Bali Too is a comment on tourism and consumerism.
The Diamantina Drover about droving on the Diamantina river.
And here’s The Irish Rover’s doing The Overlanders.
That was so subtle, I missed it at first. Well done!
Does I Come from the Land Down Under count?
Yes, which is probably why the OP mentioned it.
Four from musical theatre:
Australia (Nield) The Ragged Child
Australia (Markham) Alexander and the Terrible, Horrible, No Good, Very Bad Day
I Still Call Australia Home (Allen, P.) The Boy from Oz
Seven little Australians waltz (Reeves) Seven Little Australians
“Shelter” - Eric Bogle
No direct reference to Australia, but generally understood to be about coming home to Australia.
Kookaburra sits in the old gum tree,
Very merry king of the bush is he,
Laugh kookaburra, laugh kookaburra,
gay your life must be.
Or the far more popular version (amongst kids anyway) of
Kookaburra sits on the electric wire
jumping up and down with his pants on fire. 
And it also brings to mind a song I haven’t heard in ages, and cannot for the life of me find a version of it playable online - ‘I made a 100 in the backyard at Mum’s’
The Battle of Brisbane - The Pogues
Nobody has mentioned Monty Python’s “Philosopher’s Drinking Song”?
http://www.adelaide.edu.au/library/guide/hum/philosophy/philos_song.html
Ooh yeah, almost forgot to mention Home Among the Gum Trees
"Give me a home among the gum trees,
with lots of plum trees, a sheep or two, a ka-kangaroo.
A clothes line out the back, verandah out the front,
and an old rocking chair. "
The Outback Steakhouse song
:ducks & runs:
This reminded me of the song “Van Diemen’s Land” by Shirley Collins and the Albion Country Band. Turns out there’s a whole passel of references to Van Diemen’s Land (now Tasmania) in song, as listed here:
Add Moreton Bay to this. It is traditionally sung to the tune of Boulavogue but Andy Irvine does a fantastic version with a different melody.
try the coodabeens website, greedy.