Ningaloo reef in November/December? You've got to be joking! I love the place, and Cape Range National Park nearby, but that's the wrong time of year.
Last year I went to the Gondwanaland World Heritage Area - there are 16 National parks in this grouping, with Mount Warning being the centre of the area, being the caldera of the original volcano (one of the biggest shield volcanoes). The original volcano went from beyond the coast (there is the Giants Causeway at Fingel Head, as well as a number of other rock formations) to well inland. You can stay at the beach if you want to. If it's hot you can head into the mountainous areas, or you can just meander along the beach. Murwillumbah is the major town in the area, but it's about 30 mins from the coast. The different National Parks showcase different types of subtropical rainforest, and there are quite a diversity of tracks. and landscapes. Numbin (Australia's hippie town) is part of the area. This area is just south of the Gold Coast, so it probably isn't as crowded as the Gold Coast or Sunshine Coast which are a bit further north.
If you don't like heat, go to the Mt Hotham, Bright or Falls Creek and wander around the high country. Only problem is that you won't see the coast if you do. Or you could join a million (slight exaggeration) Victorians at Wilsons Promontory National Park, which has excellent walking tracks and lots of beaches. Many tracks are for several days, so you could avoid the masses who are all at Tidal River. Or you could go to the Prom before the school holidays, and go to the high country once school breaks. If you go from Wilsons Prom to Mt Hotham via the coastal road (go as far as Mallacoota, it's nice) and then the Great Alpine Road, you'll see some interesting scenery.
Of course, there are some walking tracks along the Great Ocean Road, so you could go to the West of Melbourne rather than the East, and visit the Otways and the Grampians as well.
There are also a lot of National Parks and walking tracks around the Sydney area. The Blue Mountains is another World Heritage area to the west of Sydney, and the suburban train line goes to where one of the National Parks starts. Ku Ring Gai National Park is to the North of Sydney, while Royal National Park is to the south. Both of these are coastal, and if you were early enough you could see some Whales (May to November). All three parks have lots of tracks.
There are loads of good places to go in other parts of the country, but it is getting hot at that time of the year, so I wouldn't really recommend any of them except, perhaps Kangaroo Island - which has loads of beaches, National Parks, and walking tracks.
