Have the Romulans travel back in time 4.5 billion years and mess up with the primordial soup on Earth preventing life from forming.
Introduce a new cunning enemy, more cunning than the Dominion and more evil than the Borg. And make three horror movies based on them.
Create a story situated 4 billion years into the future when the Sun's life is near its end, the Federation doesn't exist anymore, and you can't recognize any of the original species anymore. Depict them as hopeless and failing in everything.
Intergalactic invasion by non-humanoid ugly aliens.
The Federation discovers technologies allowing them to have the powers of the members of the Q continuum. A war between the Federation and the Q continuum destroying both sides begins.
Or... A Sith lord comes from the Star Wars galaxy and corrupts the Federation?