There are 3 types that are super-effective against Fighting: Fairy, Flying, and Psychic. For the Fairy type, get a Cutiefly. You can find them on Route 2, Route 3, and Melemele Meadow. Most of the Cutiefly have Fairy Wind and will outspeed the Kahuna's Pokemon. I beat the Kahuna with a level 15-ish Cutiefly at half health. You can also get a Drifloon at the Hau'oli Cemetery, and they might know gust, which is super-effective against Fighting types.
I hope I helped!
Source: The DB Pokemon entries and experience