Hmm, well this might be an oddity of a sort but I dont see that as a problem. Due to the Toa being the elements themselves, their spirit can mainfest in anyway it wants to. Again, like in Avatar, you had the Avatar being reincarnated each time in a different body and different group of people.
I would make it so that the visual inner representation of the elements would be an unspecified genderous spirit (adorning the symbolic mask from which later tribes took to referenciate the element they worship; the shape of the masks change with each reincarnation but the basic details of each mask are kept withing each reincarnation)...I would essentially make it so that the Elements are called Tahu, Lewa, Gali, Onua and such....however I would make it so that the actual sets (heros, Toa) would be called differently. Their gender (of the elements) would not be known since when refering to the outside hero they would have a male and female voice overlapping effect (or dependind on who is the current hero, the elements would sound ether more feminine or masculine).
They would be adorning similar masks of their respected elements (which would change due to them realising their existence). I would still make the mask relevent as objects of worship, as well as technological objects that would try to create new functions for the user, which would be different or immitating the function of the elements (as a cultural nod to their worship). This depends on how each mask was made and for who.
I think this would make it open for new characters each story cicle, while also being open for characters actually passing on and the elements being reincarnated in new individuals of unknown place of origin and figure.
The Toa of Earth coming from the Tribe of Air would be a drastic thing to happen, which would be open to a lot of different plot points.
Also in the first story you would have a male Toa of Water, while in the next one a Female, similar for the rest of the elements.