In Norway, most people I've been around use rubber boots for basically everything. Not good for backpacking, but it makes sense. That's what all the farmers do, for example. Lars Monsen actually tried that in his Canada crossing, but had to stop because his feet just got too rotten and wet, but that sort of showed how common those are there as a standard solution.
But I'm curious, Icelanders are pretty resourceful people who do a lot of outdoor stuff, by necessity, since there's not a lot else to do there. So what do they do? I'd guess whatever they do is reasonably sane and a reasonably good solution, since they do it all the time.
What you say about the streams is about what I expected, sharp rocks cold water. I don't see why you would have to necessarily take the pack off to change shoes, that just requires planning on changing them, and then changing them, that's what I would do, I'd hang them off something, unclip them, change, cross, change back. How long does that take, a few minutes? Picture it: stream, stop, unclip stream crossers, pull off shoes/socks, clip to pack, put on sandals, cross stream. That's just not very hard, nor does it need to take time if you set up the stuff right. I don't know if it's that I was raised early to understand that water and cold are not good combinations for your body and maintaining comfort, safety, or what, you know, snow, cold, etc, I mean, it is understood that walking through a stream in your shoes and socks when it's cold is just a very bad idea in winter, or when it's cold and blustery and little heat exists to dry things that are soaked through, for example. I'm going to just leave this as something that makes no sense to me I think, and not think about it more.
What is needed is UL tevas, tevas are fantastic for this purpose, ideal. I used to always bring them, that way I could also go up and down rivers creeks on expeditions. Keep in mind tevas were originally invented for river stuff. And people on bpl backpack in them too, which means, to put matters in a different frame, using teva like shoes for areas with frequent stream crossings, they have thick soles, they grip well, and you can easily backpack in them. Then when the stream crossings slow, you change back to the hiking shoes. But I have to admit, I have not found the perfect mix between light weight and solid soles, teva just is not going for that market, nor does it appear that anyone else is.
I still just do not see the point of dipping my feet into water all the way and soaking my shoes, that's just something I wouldn't do as a rule, and I particularly wouldn't do it in arctic terrain/climate, but I can see the other things you noted, but if you attach the other shoes to somewhere on your pack that you can reach without taking it off, the change doesn't have to be that time consuming.
To me, sometimes this UL stuff at times just loses site of the functional part of gear, ie, the weight should reflect the function required, not function dictated by weight. So if extra wool socks, some solid sandals, and lighter hiking shoes is what function calls for, that's what I'd bring, base weight with UL gear is so low that there's plenty of room to add gear that you need to deal with more challenging terrain and conditions, but, again, I'd just see what the locals do and figure they have it pretty much figured out.
By the way, I've been searching for a year or so now for odd out of the box solutions to the entire stream crosser/camp shoe thing, trying all sorts of things, one thing I did discover is that if you take normal flipflops and either tie or sew flat cord or webbing to them with a tightener, ladderlock, cord lock, you can get them to really stay on your feet quite well, at almost no weight penalty. But you have to pay attention to the soles, some are, as you noted, very slippery, but others are quite good and stick decently to surfaces. My latest thing to try is cheap chinese sandals, the kind molded in one piece out of a sort of tough foam, weigh close to nothing, but are ok for light use, again, I make a heel strap to keep them on, that really works, and is light. Would be better if someone like teva made a version that was tougher, but they don't. I've thought of trying to make my own, all you need is reasonably non slipping soles, teva like toe/heel attachments, with light straps instead of their heavy stuff, would be super easy shoes to make. Would weigh something like 5, 6 ounces I believe if done right.
By the way, I think that the softness of the rubber is a key factor in how well they handle slippery surfaces, so soft rubber soles that are nice and sticky will tend to wear fast, or faster. I know all my trail runners have what I would consider mediocre, at best, traction in slippery conditions, trekking poles help in that situation, but it's something quite noticeable when comparing them to their heavier hiking shoe brothers. Also tread depth I think makes a pretty big difference there too.
There's also a mind component, if you treat a stream as not part of the path, but as its own thing, and just stop, handle it, like you'd handle deadfall, or a landslip that pulls away the trail, I think a lot of these things just vanish in terms of being obstacles, and just become one more feature of the trip. Not sure if that' makes sense, oh well.