I have a vast series of scenes, characters, and stories coming together in my head, which I have yet to transcribe to an actual story on paper. I have notes, and many of them, but I cannot seem to connect the time periods without seeming too cliche and/or predictable. I need advice on how to go about the different timelines while also maintaining the direction and structure of my story.
There is a book here in Brazil called "Batalha do Apocalipse" or "Battle of the Apocalypse" in english. It is a christian mythological book with immortal angels.
This book passes from ancient times until modern days. There is a book series from it called "Sons of Eden" that does almost the same thing. As far as I know, once a mission/objective/journey in one time period is completed, it passes to the next. For example, he was in WW1 and want to pass to WW2. But what he does in between? The author sumarize the events and how the characters react to it, and he also gives a pretty good historic background.
If there is something important to the characters happening between WW1 and WW2 he creates scenes that "resumes" the importance of that event. For example, the character starts to live in another country, so he narrates his arrival in there, his impressions and his new house.
You must show only the important and tell what is necessary.
I have not read the books, I only know this because of my girlfriend who reads it. I may edit this answer for better understanding and gather some information with her about this.
Also, depending how long the time passes in your book, I think you should see the time passing just as if it was a day or a week. After all, for immortal beings, what is a hundred years? "Nah, it's more like a week."
You need to make a very clear distinction between imaginary history and story. It seems to be quite common for aspiring writers to construct elaborate imaginary histories and then struggle to write them down because they are not actually stories.
We can't tell from your question if what you have are actual stories or simply imaginary history, but the fact the you describe your attempts as cliche and predictable is an indication that this may be the issue.
A story has a very specific shape. At its heart it consists of a character who values certain things and has a desire for something else. To attain that desire, they must sacrifice something else they value. They are reluctant to make this sacrifice, so they try different ways to attain their desire, but are rebuffed each time, leading them to have to make a fundamental value choice. The story then proves through action that the choice has been made and shows its consequences, for good or ill.
There are a few basic stories, all of which involve this confrontation of a questions of values in one way or another. We retell these basic stories over and over again. In that sense, every story is cliched and predictable.
What makes a story feel fresh and new, or keeps a classic eternally relevant, is not some novelty of storytelling. It is the freshness and perception of the telling. We don't want to see boy get girl because we have never read a courtship before, but because we want to see this particular boy, who we have come to know as if they were a member of the family, get this particular girl, who we have come to know as if she lived next door. We want Spidey to get MJ and Mr. Darcy to get Elizabeth Bennet because we are interested in these characters in particular, not because we are expecting new frontiers in romance to be revealed to us.
Take your imaginary history. Find the stories in it. Write those stories. Include the parts of the history that are relevant to the story you are writing. Omit everything else. If there is no confrontation with values in the the next 20 years of your characters life, gloss over those 20 years in a paragraph and get to the next confrontation. Make sure that your characters are real enough that we recognize them are real people. Make sure you are writing this boy gets that girl, not just boy gets girl.
The rest will take care of itself.