In 1350, how mutually intelligible would Icelandic, English, and Scots be? Scotch and Irish Gaelic? Welsh, Cornish, and Breton?

Welsh would not have been mutually intelligible with Cornish and Breton, but was very similar grammatically. Modern Cornish is somewhat cobbled together from Middle Cornish and Late Cornish, so it's more similar to Middle Welsh (at least in some ways) than Modern Welsh is. The vocabulary and a few very important aspects of syntax were different enough to prevent comprehension, but a Cornish speaker would have a very easy time picking up Middle Welsh and vice versa.

Modern Welsh: "Dw i'n dy garu di." Middle Welsh: "Mi a'th caraf." Cornish: "Me a'th car."

There are reports of Cornish sailors being able to speak to Breton sailors well after the Middle Ages, and Old Cornish and Old Breton are generally considered to be geographical terms for the same language. By 1350, they would have still been fairly similar that mutual intelligibility was certainly likely.

Irish and Scottish Gaelic were part of a dialect continuum that has since been broken up into isolated pockets. We can still see some of this in the Gaeltacht regions of Ireland. The Irish of the northernmost Gaeltacht shares many features with Scottish Gaelic that are absent in the other dialects of Irish. In 1350, a common register existed called Classical Gaelic that was used in both Ireland and Scotland. Classical Gaelic ceased to be used after the Flight of the Earls (there was no one left to patronize literary arts in Gaelic).

Icelandic would not have been remotely comprehensible to an English or Scots speaker. It is, however, very similar to Old Norse. An Icelandic speaker today can read Old Norse texts quite easily. A Swedish or Norwegian speaker can probably read them with a little bit of work, so one from 1350 would at least be able to make themselves understood to an Icelandic speaker.

English and Scots are fairly mutually intelligible today. Scots is a Germanic language and descends from English, so it would not be intelligible for a monoglot Scottish Gaelic speaker.