Not to be controversial, but I don't thing the story would have changed much at all. Middle Earth seems to revolve around fate and destiny and there are characters in Middle Earth that have already seen the general outcomes of events . For instance, it was prophesized by Glorfindel that no man could kill the WitchKing. Prophacies by qualified characters in ME (such as elves) can pretty much be taken as gospel. So, IMO, the whole story is already pre-ordained. If Gandalf had not fallen in Moria, I believe that minor details may have been altered slightly, but big events such as the death of Boromir would have still taken place because it is that character's destiny to die.
