Ed,
Re your timing, most of the greens maintenance occurs in Feb/March, so you should be OK in April. Personally, my all time favourite time of year to play golf in Melbourne is May. The greens are at their best, the weather is still fairly warm, and the wind is generally lighter. (It can still blow 40mph any day of the year though!)
I can't add much more to the advice above, except to say that I would send the letters to the clubs as early as possible and base your itinerary on the responses. I agree with all who said it will be impossible to play a private course on a Saturday, and Sunday will be tight as well - so play Barnbougle all weekend, there are worse fates in life!
Regards,
George