[The Might]

...or maybe they could have flown with the help of the Eagles all the way to Mount Doom?

No, but seriously now, I wouldn't go so far so as to speculate that Gandalf "had to" use that way, especially since it wasn't his decision only in the end, and the outcome could have been different.
I think this would be the topic of another thread.

Actually, if I think about it, Moria was a strange choice. Gandalf definitely felt something was wrong down there, since they had had no news from the Dwarves there, it was clear something had happened, but not what.

The Gap of Rohan was more dangerous, since reaching it meant going further on the road through Dunland and by the time the Fellowship would have reached Rohan, Saruman would have already sent his troops to attack Theoden.

But I just had another idea.
We know that:

[FONT=&quot]Only here [the Fords], south of Isengard, was it possible for large forces, especially those heavily armed or mounted, to cross the river. ~ UT, The Battle of the Fords of Isen[/FONT]

So it was not possible for heavily armed Uruks to cross anywhere else, but what about the Fellowship?
They didn't have heavy armor (ok, maybe Gimli would have had to give up some stuff) so they could try.

Also we are told:

[FONT=&quot]Beyond the Gap the land between Isen and Adorn was nominally part of the realm of Rohan; but though Folcwine had reclaimed it, driving out the Dunlendings that had occupied it, the people that remained were largely of mixed blood, and their loyalty to Edoras was weak: the slaying of their lord, Freca, by King Helm was still remembered. Indeed at this time they were more disposed to side with Saruman, and many of their warriors had joined Saruman's forces. In any case there was no way into their land from the west except for bold swimmers. [/FONT]

Well, Hobbits and Dwarves aren't bold swimmers, but I'm sure that with help from the others they would have made it across eventually.

So why not go from Hollin cross the Glanduin, do into Enedwaith, preferably closer to the coast, cross the Isen (or the Isen and the Adorn, depending on what place would be chosen for the crossing), pass the Druwaith Iaur and finally enter Gondor.

Of course the plan was not really taken into consideration, since the road might seem too long, but wouldn't it have been an option?
Or option 2, after crossing the Isen south of the Fords, head east towards Helm's Deep. Definitely they would have made it in time this way as well.