We took our youngest on his first long plane ride (DEN-LHR) at 8 months and he has been flying ever since. Our second has been flying since about the same age. They are now 14 and 11. The one problem that we always faced with long trips like what you are considering is that kids, in general, do not recove from jet lag quickly. Under about age 3 our kids would typically wake up in the middle of the night and stay awake for several hours. It would usually take 3 to 4 nights before their sleep schedule would mesh with the new time zones. I think that a trip to Australia might keep your kid out of sync for many days considering the time change from east coast.
However, Hawaii would not be quite so bad. Especially if you stayed a day on the west coast on the way over to break things up and allow for a bit of time adjustment. Hawaii is about as kid friendly a place as you can find. All of the places we have stayed have either had kid programs or could arrange babysitting so that you and your wife can manage some time alone without much trouble.
Hope this helps.