No se si tengas conocimeintos de Hex pero es sumamente facil.

En el editor Hex de tu eleccion vas al offset $17844 y cambias el valor 00 por cualquiera de tu eleccion del 0x00 al 0x07. Esto para el protagonista.

Si mal no recuerdo los primeros tres colores son:
00 = Rojo
01 = Azul
02 = Verde

Cuando hagas las pruebas seria bueno que nos dijeras los otros colores :D

Para tu rival es el mismo proceso, pero en $17856.

Saludos!

PD: En caso de que el colore del rival no cambie, quiere decir que tienes que cambiarlo manuealmente con algun editor de mapas, esto en cada mapa que se encuentre tu tival.

PD2: Hay un tema de Dudas de GBC, para que ya no hagas temas y mejor preguntes ahi