Most places in Europe are good fun - the difference between Australia and Europe is that in Europe you only have to drive to the next city / town / village to experience a different culture, langage, attraction etc. The place is crawling with cool places to visit, so all you've got to do is head out in a random direction for a unique adventure...
My personal reccomendations, for off the beaten track:
UK - Get down to the far southwest (where I'm from
) for quaint villages etc), Bath and Stonehenge are on the way. Scotland is great, countryside & Edinburgh.
France - would be an awesome country to cycle around with a tent in your backpack, for a month or so, picking up some cheap wine / bread / ham / cheese for lunch every day. *drool*
Amsterdam - ok you said avoid touristy areas, but this place is amazing to see, plenty to do even if you dont smoke weed. Bike friendly too, just watch out for the trams.
Austria - Never been here in the summer, but friends have and apparently the place is lovely - pristine lakes, castles, alpine meadows, etc.
Germany - I'd love to visit the black forest region here, and eat all the meat they have to offer. And drink the beer. Berlin is great to visit if you like cities.
Greece - go island hopping. Some (hopefully not all?) are as bad as spain (english & german tourists), but there are a lot of islands, surely some arent too bad. Maybe book a sailing trip?
Hmm - lots to do, too much really. If I were you, I'd just get on a bike and go riding around and see where the road takes you!
P.s. where are you - shepparton or somewhere?