What if Ned was betrothed to Catelyn right off the bat?

[Angel Eyes]

Say if Lord Ryswell demands that Brandon and Barbrey marry after Brandon sleeps with Barbrey and Lord Rickard accepts, then offers Ned as a replacement to marry Catelyn. Can he do that? How pissed would Hoster be?

[Yukle]

That'd be extremely unlikely. GRRM correctly shows how women were used as bargaining chips in these games of high-stakes politics.

The Starks and the Tullys are as highborn as you can get without being the royal family. Lord Rickard would never accept such a deal, as it'd completely ruin literally years of planning. Everything from the Tourney at Harrenhal to the marriage of Rickard indicated that the lords had been planning their revolt against Aerys (or perhaps forcing him to abdicate) for years. The marriages were essential to ensuring that their fates were tied, and if it came to war they'd have allies.

[Ralphis Baratheon]

Hoster Tully was to power hungry and intent on advancing his House through marriages to except a marriage between one of his daughters to a second son who was set to inherit no Castle or lands. Perhaps if Rickard had rebuilt Moat Cailin for Ned  after he was born then Hoster might consider it. It would have been expensive but the Moat may have been able to make the North's money back if they installed a system of charging tolls for those traveling North, like the Freys do with the Twins. 

[Dorian Martell's son]

3 hours ago, Angel Eyes said:

Say if Lord Ryswell demands that Brandon and Barbrey marry after Brandon sleeps with Barbrey and Lord Rickard accepts, then offers Ned as a replacement to marry Catelyn. Can he do that? How pissed would Hoster bee?

Nothing changes. Brandon still dies, Jon is born, bob becomes king and the books happen as written