I don't think there was another way to pass the Ephel Dúath. Frodo and Sam tried to cross the smaller Morgai, but couldn't find a possible way. If it was impossible to pass the Morgai, it must have been at least as impossible to cross the Ephel Dúath. 'Ephel' even means 'fence', and I'm sure those mountains didn't carry that name for no reason. I imagine them like an evil (miniature-) counterpart of the (almost) unpassable Pelóri. I doubt there was a different feasible road but the Black Gate and the Morgul Road/Cirith Ungol. The Ered Lithui sound a bit nicer, but not really that much.
A similar question just popped up in my mind: Why did the fellowship try to pass the Misty Mountains by the pass of Caradhras? I mean, the Misty Mountains are an incredibly long mountain range, so it is quite hard to imagine there was no other pass south of Rivendell, preferably crossing a mountain with a more trustworthy reputation.
PS: What about Fladnag and Odorf?
And wouldn't it have been an incredible showdown for Gandalf and the Witch-King if they would have done a magic song contest at the Black Gate like Finrod and Sauron used to?
He hissed a song of wizardry... 