Alright, let me take a shot at this. Surely one of those idea's is good:
1: An evolution by having your pokémon in the first slot of your party, and then visit one of those hawaiian dance performances, could be a dancing like pokémon, or maybe one who likes singing and dancing? (bellosom is kinda in the way for this one)
2: Pokemon that evolves when playing a surf minigame with them. Like a dolphin that in Pokémon lore follows ships and surfers and protect them from wild pokémon (or something like that)
3: Pokémon that evolves into a different type/color when on a different Island than the one where you caught it(kinda Darwin like) Edit: just saw that my idea is kinda like that of Bigdog ;)
4. Pokémon that evolves by being around people, (talking with NPC's or online interaction needed to evolve). Could be a really social pokémon.
5. Pokémon that evolves by letting it use/eat a lot of berries in and outside of battle. Kinda like a bird or something like that.
6. Pokemon that evolves by combining 2 pokémon, kinda like backwards of Shedninja. Maybe a kind of plant, and a a sea creature, that benefits that much by being with each other, that the plants grows around the Sea creature, so that the sea creature has camouflage, and the plant protection.
7: Pokémon that evolves by letting it faint with high friendship. It is sorry for you, and wants to grow to become strong enough for you.
8: Pokémon that evolves by leveling it while being poisoned (saw this one online somewhere). Maybe it gains a poison resistance or something
And im out of idea's!