1. Probably not. While a marriage to Benjen would preserve the victorious rebel alliance and firmly bring the new young Lord of Winterfell – notably the one Stark with no attachment to the surviving elder statesmen of the SA – into the coalition, Hoster Tully would have limited means to make it happen. Catelyn is objectively a nice dynastic prize, even as a widow in patriarchal Westeros, but Hoster would be lacking a noticeable bargaining chip to use to advance the match like he used the promise of the support of the Riverlands in the rebellion with Ned, or the personal friendship and similar political objectives that he shared with Rickard Stark which produced the Stark-Tully alliance in the first place. He can not even promote it on the idea of honoring the betrothal agreement between House Stark and House Tully because Ned already honored that when he married Catelyn. What he could do, though, is promote the strategic alliance, and, if Robb existed, use Catelyn’s proven fertility as an endorsement for her merit as a wife, as he did with Lysa. After all, a House that has dwindled down to one surviving member is one in a desperate need for heirs asap, and Catelyn’s obvious fertility that enabled her immediate pregnancy on marrying Ned would only be a boon for a House on the verge of dying out.

However, this is where Benjen’s distance from his father’s schemes might undermine Hoster’s efforts. Unlike Ned, Benjen has no personal connection to the rest of the SA players and no reason to favor this match. He would have no trusted counselors who would speak for it – no Maester Walys to broker it, no parental figure like Jon Arryn to encourage it, and the possible exception of Maester Luwin could easily get drowned out by Ben’s other counselors who 1) would almost exclusively be northmen and 2) are unlikely to support marrying Lord Rickard’s last surviving child to a southron – the same southron who had “gotten” both Brandon and Ned at that, as someone like Barbrey Dustin would put it. It can not be said that Catelyn would be a particularly popular choice for Benjen’s bride in the North as a Seven-worshipping southerner who had never even been to the North, where the common sentiment about southerners is crystallized by the Greatjon’s “[w]hat do they know of the Wall or the wolfswood or the barrows of the First Men? Even their gods are wrong”, or where Lord Rickard’s “southron ambitions” are still talked about so contemptuously two decades later. Certainly, that scorn would be at an all-time high on the heels of the rebellion, when Lord Rickard’s heavy association with the south ended in war that cost the North thousands of lives, claimed the lives of four Starks in short order, and culminated in the entire region teetering on the edge of instability being one teenager away from a major succession crisis. That’s not an atmosphere where a southron Lady of Winterfell would be favored. Too, the fact that Catelyn had been promised/married to both of Benjen’s older brothers might be a mark against her in the eyes of the northmen with an effect that ranges from reluctance to see yet another Stark marry the same woman who got his two brothers (remember Barbrey Dustin’s “Catelyn Tully got that one as well” in reference to Ned. In the same vein, why should Catelyn Tully “get” three Starks when there is a number of perfectly suitable northern girls available?), to an aversion to Catelyn’s specific person, not just as a southron stranger but as an harbinger of bad luck and death, a Red Widow in the fashion of Rohanne Webber so to speak.

Finally, there is the matter of Benjen himself. It’s been speculated that he joined the Night’s Watch in OTL out of lingering guilt over the rebellion, which would only multiply if the war claims Ned too and Ben is left as the sole surviving Stark. I’m thinking of
Ned’s guilt and insecurity over how everything he had was meant for
Brandon, which is likely to be present in Ben as well making the idea of him taking the
place of not one but two brothers and marrying his late brother’s wife harder for him to accept. It’s also likely that Ben would develop the same dislike for the south and southern politicking that we saw even Ned display despite his great affection for Robert and Jon Arryn and his familial ties to the south. In that context, the chances of Benjen consenting to marry Catelyn are not great.

2. Not a great chance for RobertCatelyn either, imo. Jon Arryn was a shrewd statesman who knew the value of Robert’s hand and how best to utilize it to augment the new regime’s position and shore up their alliances in the wake of the rebellion. Now, matching Robert and Catelyn could be an affirmation of the rebel alliance, which, in the case of Winterfell closing off to a visible alliance, would certainly help in publicly presenting the coalition of Baratheon-Tully-Arryn as a strong unit. It could also be a method of distributing favor to a House that supported Robert during the rebellion, sending a message about how loyalty to the new king will be rewarded. However, Cersei Lannister is still the most beneficial political match for Robert; after all, Robert already had the Tullys tied to his kingship through Jon’s marriage to Lysa, and he had just made Jon Hand of the King making Lysa the second most powerful woman in Westeros. Through Jon, it’s guaranteed that House Tully’s interests would remain in the king’s ear and that he, in turn, would have Riverrun’s support. It might, then, be a waste to use the most valuable marital prize in the land to gain an alliance with a House already allied with the crown, when Robert’s hand would be better used to bring in another house with less ties to the new dynasty, especially one with far superior wealth, manpower and strategic importance like House Lannister. Jon Arryn wanted to tie the Lannisters to their side that he essentially waved away the murder of Elia and her children in favor of reinforcing Robert’s alliances, and I don’t think he’d be any less likely to recommend that match to Robert in this AU.

3. It’s a maybe, maybe not in the case of Stannis. On one hand, a match between Catelyn and Stannis would accomplish the same aforementioned goals of strengthening the SA alliance, but on the other, Jon Arryn picked Selyse for Stannis to send a pointed message to the Tyrells, which is arguably more important to the stability of the new regime. Considering that the Reach supported the Targaryens on the field during the rebellion and their overlord Mace Tyrell besieged Robert’s two brothers for close to a year in Storm’s End, Jon Arryn needed to check the Tyrells and guarantee that their Targaryen loyalty won’t lead them to take up arms against the crown which is what he accomplished through matching Stannis with Selyse Florent. As both Jaime Lannister and Olenna Tyrell tell us, the Florents are the Tyrells’ most troublesome bannermen who are are not shy about their superior claim to Highgarden to the former High Stewards (who only got their seat by the grace of the ousted Targaryen dynasty). By wedding the king’s brother (and sometime heir) to a Florent, the crown effectively sent a clear message that Robert may have been gracious enough to forgive the Tyrells but he has a contender claimant to Highgarden in his back-pocket whose “whining” he might just listen to if the Tyrells think to step out of line. That’s not an insignificant political move so I don’t know if Jon Arryn would do away without it in favor of a match to Catelyn. Ultimately, it’d come down to which objective the Hand of the King deems most beneficial to the infant Baratheon dynasty.

Though I’d wonder if Hoster Tully would desire this match in the first place? Stannis definitely has his merits: he is the king’s brother and sometime heir, a lord in his own right, and the Master of Ships, all of which would normally be a good way for a House to guarantee that their interests would be presented to the king. However, Stannis isn’t exactly a proponent of courtly games and favor-currying, his relationship with Robert is notoriously turbulent, and Robert would have just named him as Lord of Dragonstone at the time rather than let him have the wealthier Storm’s End – a move some people, including Cersei and Stannis himself, took as a punishment and a sign of Robert’s anger at his brother. I don’t know if these are good odds for Hoster to pursue this match.

4. As a brief sidebar, Jon Snow’s situation would be completely different if Ned dies at the Tower of Joy. Howland Reed would be the one hearing Lyanna’s last words and coming up with a plan to conceal the infant which might not even entail claiming the baby was Ned’s. Indeed, it would certainly be much harder for Howland to convince the world that the famously honorable Eddard Stark fathered a bastard that Howland knew of and happened to pick up on the way back from Dorne, and Brandon was too long dead for Jon to pass as his. If, by some stroke of luck, no one questioned Howland’s story, it might be a risk for Ben to keep Jon at Winterfell for everyone to openly wonder about his paternity. Moreover, Jon, as the purported male child of the previous lord of Winterfell, would still pose a political danger to Ben’s line so whoever Ben ends up marrying would still not take kindly to his presence in Winterfell, even more so if Ben does marry Cat and she has to contend with the though of her dead husband’s love child growing in front of her when her own child was dead.