You need to define "civilized" here. Tonga and Hawaii had pretty unified states, and eventually Hawaii was unified under one of these states. Sure, they had outside contact by this time, but that isn't much different than Europeans selling cannons in Vietnam. A lot of smaller Polynesian islands had local states as well.
One thing which would help is having the Polynesians keep sailing east instead of stopping for a many centuries. If Hawaii, etc. are settled earlier then there's perhaps more chance for complexity.
For a real interesting choice, get the Bonin Islands (geologically Oceania) to remain inhabited by the Micronesians who once lived there, and get them in contact with Japan to get a small (few thousand people max) East Asian cultured Micronesian state, although like Ryukyu they'll be heavily Japonicised and eventually conquered. Galapagos, also geologically part of Oceania, adopting elements of Andean culture if the Polynesians settle it, would be cool too.
There's other ways too. New Guinean civilization would spread into Australia inevitably, while perhaps you could do something with the Torres Strait Islanders. The islands of Roti and Savu, right north of Australia, might somehow be able to spread themselves or their culture to the Northern Territory or Kimberley. Finally, early settlement of New Zealand, especially if the Maori bring pigs or chickens, could result in some bigger Maori states. New Zealand with more contact with the outside world would be good too, although the best potential Maori New Zealand would be one where instead of kumara, they can get potatoes instead from South America.