I think I actually take issue with the way you're framing this:
Indeed, I have no idea on how to conciliate the no-side effects rule implied by immutable types and pure functions and the premise of OO, where methods modify instance state in-place, which is obviously side-effects.
I wouldn't say that mutative operations on object fields is a core "premise of OO." Not at all (although conversely I do think that immutability is a core premise of FP). To me, OO is a way of thinking about program modularity more than anything else.
In my (perhaps twisted) mindset, even Haskell -- a language whose advocates often cringe at OO-style thinking -- nevertheless embodies some OO concepts, in the sense that it has a module system, various ways of encapsulating implementation details of datatypes, etc. And on the flip side, although it's exceptionally clumsy and aggravating, my Java code tends to make heavy use of basic functional concepts like currying.
In other words, I think the two approaches are complementary in a sense.
Now, at a less theoretical and more nuts-and-bolts level... Let's say you have something like:
class Foo(val a : A, val b : B, val c : C) {
def setB(newb : B) : Foo = new Foo(a, newb, c)
}
... so you can say newFoo = foo.setB(b)
as you suggested in the original post. I'd say this is totally fine style, and not cause for concern (about performance or readability or anything). You'll see plenty of this with the immutable collection classes in the Scala library.