Why not take a quick hop to Lanai or Molokai? I would take Ohana by Hawaiian, not sure how reliable the improved Island Air is yet.

You can also fly into the topside of Molokai from Oahu, might as well because its just as hard getting there even when you're on Molokai.