[@Baklava] Ah. Duly noted. My apologies for not getting that the first time when you noted about looking at the roster! 

Will push the Stalfos and Darknut ideas to the side for now. Perhaps they could all be my sort of "last resort" ideas if i couldn't come up with something else, though it should be no problem at all to come up with a different idea or two for a character as well that will, hopefully, better meet your desires for the RP!

As for the Rito idea i put out there, i will respect your wishes and completely abandon the concept as a possible idea. Will also throw out the Twili idea as well. Did not mean to sound like i wanted to put in a "game-breaking OC" of some sort in there, as while the idea did actually occur to me that they could blow future details, i was at first somewhat thinking they could be amnesiac or not learned in history as you noted to avoid "historical spoilers" as you said. Still, i felt like throwing the idea out there in general to test the waters and see what is and is not acceptable at this point in regards to that, as it were! So no Wind Waker races! 

So, with all of what you said in mind, there are about two or so other ideas for OC's i want to pitch, to see if they better meet what you want for the party of characters. So without further waiting, here are my ideas:

[u][i][b]First Idea[/b][/i][/u]: A young, Hylian woman whose parents moved near the Gerudo Desert just shortly after she was born due to her father getting a job working on the bridge to the Gerudo Desert. It was here that her family was robbed one night by a Gerudo raiding party, who as a result of her parents fighting back ended up killing both of them. As a result, the young female Hylian baby was taken back by the Gerudo along with other plunder. 

From here i believe this OC can take one of two alternate paths i thought about for their history:

1. They could be raised as a "regular" among the Gerudo and grow up being treated like one of the Gerudo, eventually learning of 			her Hylian heritage many years later by accident and ends up setting out on into Hyrule to try to discover her past, which event eventually leads to her having the dreams and such that bring her to where the rest of the party is in the graveyard. Down this path the OC could be a more combat-focused Gerudo-related character that differs from Veitaru in that sense. 

She could be a skilled archer, horse rider, perhaps even be a dual-sword wielder and some Gerudo-esque combat skills and desert expertise and such to add to the team. 

2. They could be taken back, only to be taken in by an older Gerudo mystic and magic user who, while not being at the level of the 400 year old witches (Twinrova) who raised Ganondorf in Ocarina of Time is still a strong magic user who acts as an elder to the tribe. It would be in this highly respected magic user's household that this Hylian girl would grow, being kept mainly to the house due to the disgust an amount of her "Gerudo sisters" would show to her as compared to the few who seemed to accept her as one of their own. Learning magic from her surrogate mother, eventually the Gerudo mystic/elder who raised her would die, and knowing that a portion of the tribe will still never accept her sets off to not only try to determine her own family history but also to see the world she had been shut out of in the past (before having dreams and meeting with the party of course) with supplies given to her by those who came to care for her and accept her among the tribe. 

In this case (and my favorite of the two options here) the OC would have good and wizened desert expertise taught to her and trained into her by her surrogate Gerudo mother, magic skills that could either be utility-based magic (which could be useful considering some of the OC seems to have an amount of combat magic between them) or a mix of utility and combat magics to allow her to support in combat while also providing things like healing to make her a versatile character in the party in regards to magic. Further, she could have trained in the bow and perhaps a single weapon, if i were to justify her surrogate Gerudo mother calling in favors to get her trained in the use of a weapon like dual-sword or (not "and") the bow and arrow to help allow the girl to protect herself in the harsh desert the Gerudo live in. In fact, she could possibly know medicine in some part if her mother taught her as well, a thing that could come in handy to give her a "healing" sort of role if combined with her possessing magic.

[u][i][b]Second Idea[/b][/i][/u]: A Goron (male as they all are of course) who is relatively young for his race at the age of 70 years old. His father was a skilled smith among the Gorons, but the OC himself was best suited to...explosions. As in, he was great with explosives and bombs, and learned how to make them rather well. While he enjoyed dabbling in explosives, he also learned to wield a large hammer in combat on top of the rolling and still somehow knowing where he's going that Gorons are known for. On top of the natural strength and toughness the Gorons are known for, he could be a good addition to the team for brute force and another OC who can deal with fire rather well. He would make his way into Hyrule out of curiosity to see what Hyruleans have learned about explosives and see if he could learn anything new to add to his hobby. After all, while he is a Goron he is an intelligent Goron who enjoys explosives but is not an idiot otherwise by any means. At the same time, during this trip he could begin to have dreams and move to go to the graveyard the dreams direct him to in order to see what is going on. 

[u][i][b]Third Idea[/b][/i][/u]: This one might be the most odd, but if it's rejected i will not argue. What about...a Minish OC? 

They could be from a pocket of Minish that stayed when the door to the Minish world closed at the end of the Minish Cap came, desiring to live in and stay in Hyrule. Living in Hyrule's Castle Town through the centuries even after the forest some of their people once called home was lost, this group of Minish composed of all kinds of Minish who gathered there after their other homes were destroyed or changed over time by other events would have moved with the Hylians as they moved from place to place. The magic that kept them invisible to adults began to fade away and eventually disappeared over time as well, leading them to become more reclusive from Hylians and humans as a whole in order to help preserve their people over time.

The OC themselves would be a Minish who has learned magic from one of the last members of his kind to have been trained in and honed in the art of it. Rather than combat magic, this magic would take the form of general utility magic and especially a form of "size-altering magic" to allow them to alter the physical size of themselves, objects, and even other living things if the need arises. This "size-altering magic" could have originated among the Minish still remaining in Hyrule after the stumps they used to change size back during the time of Minish Cap were destroyed and became effectively nonexistent over time. Further, the OC could sport general utility, medicianal, or other support skills on top of some skills with a sword or other weapon in order to help them fight and not smiply be a hinderance to the group as a whole. However, they could play a support role as a whole for the party of characters, being educated and intelligent as well. 

This OC could also be male or female, and after having dreams they use size-altering magic to grow to human-child size or such in order to set out on a journey to the graveyard. This is probably the strangest of my three ideas, perhaps the greatest stretch. Even so, i would hope this sounds more feasible than the time-defying and other hard ideas you mentioned before!