Or set it up North in Angmar. The Witch King had plenty of time up there to breed monsters that would challenge a high level party.
Shelob's Lair/Dol Guldor would make good climaxes..
This also implied that without Sauron's binding influence, the evil creatures of Middle Earth (the orcs, Uruk Hai, trolls, etc) also lost their potency.
However, you can restructure the setting as you see fit. There are certainly plenty of evil men available and you can create new forms of evil as well. What is a mortal world without the presence of something evil to tempt it?
First, go to your players and see who they want to play. If one of them wants to play, say, a daughter of Aragorn, then that tells you that it has to be set at least a generation after the fall of Sauron. Probably a long, semi-Elfy generation, like a century or so.
But, you should run a prelude. Design an adventure that takes them from levels 1-3 and use that to depict a moment in their collective "youth." On the one hand this will help to bond the characters and make the "party" aspect of it seem natural later on. And on the other hand it will help to illustrate the differences in their aging rates, if you've got humans and hobbits and elves and such all in the same group. Remember to Foreshadow the Ominous Doom, but keep it Vague. Give the players a glimpse of whatever Fantastic and Terrifying Location you think they're going to end up in for the last major encounter in the campaign, but make sure it's only a glimpse -- like the way the One Ring is thrown into the fire and Gandalf gives a little bit of scary information on Mordor. Make the adventure something kinda cool, the introduction of the characters into the terrifying but sweetly-rendered FX of the supernatural world beyond their homes. Look at wights in barrows, maybe, for something that people who only watch movies won't recognize.
Then, years later, you've got a bunch of 3rd-level characters who are ready to do stuff.
As for what the actual threat could be -- well, one suggestion is that Middle-Earth is actually kind of a small place, if you just look at LotR. Traipsing about in the territory already explored is part of the reason why you play such a campaign, but at some point you're going to have to progress into new lands. A threat from a far-off place -- maybe another world entirely? -- would be a good excuse to send the PCs on a voyage of discovery, which is what LotR is all about. Just make sure to focus on the familiar aspects now and then in order to maintain the feeling that it is a Middle-Earth story.
How 'bout this -- Narnia invades Middle-Earth! Only make it a scary, twisted Narnia. Rather than just talking animals and sylvan creatures and such, make it a world of lycanthropes and evil faeries. The world of Anniar (forgive me), ruled by a savage werelion who demands total obedience to his every whim or else he eats you. Include a rag-tag resistance lead by David Bowie.
And to include the word ring in there somewhere, use the rings from The Magician's Nephew. Say that the lycanthropes of Anniar have got their hands on one of these rings, and they're using the wells to travel from world to world, conquering everything in the name of their cannibalistic empire.
The PCs, in their prelude adventure, should find one of the rings (I forget which color it should be) in some sort of treasure. Then, later, after everyone has grown up, Anniar invades Middle-Earth. The PCs have to figure out where they're coming from (heroic), put a halt to the invasion and acquire the alliance of other threatened worlds (paragon), then launch a counter-attack to end the evil empire (epic).
For alliance/enemy worlds, I suggest places like Zo (lots of emeralds in their architecture), Aephyborre (a conquered world that supplies Anniar with lots of barbarians) and such. But you shouldn't even bring those up until late-paragon, I'm thinking.
I hope you find something useful in the above ramble.
If you want to use the period when Morgoth is released by the Valar but before the War of Wrath that reshaped Middle Earth, that would be considered the period of the later half of the First Age.
Humanity was still in its infancy. Elves and dwarves were fairly numerous. No mention of halflings/hobbits (as far as I can remember). Evil was abundant with orcs, trolls, ogres, dragons, giant spiders, werewolves, vampires, Balrogs and of course Melkor/Morgoth (the fallen Vala) and Sauron (the fallen Maia).
Possibly open up with tales of dragons long thought dead remerging, a bright star which seems to sail the skies, and a gathering of orcs and goblins unseen in centuries. Possibly lead up the discovery of relics from the first age until I feel they're ready to take on Sauron and possibly Melkor himself at epic.