That was basically just the process of creating bridges back then, it's not far off from how it works today...

I don't think that was an avoidable issue, you need to build temporary support structures while bridge building is in progress. In other words, if an extensive support structure is a deal breaker for you, it turns out you're not building a bridge today.

To construct it they would have had to build a support structure nearly a thousand feet long, across a river, that could take the weight of a masonry arch bridge nearly a thousand feet long until the keystones could be put in. Not hard to imagine why it got rejected.