I don't see how immutability makes much difference to garbage collection. Garbage collectors don't look at the value inside memory they are collecting, only whether something live is still retaining that part of memory. Whether the value is mutable or immutable has absolutely no bearing on the performance or logic of the GC. Either something is still using the memory, or it is free to collect.
Also you've just described existing GC systems - The Java G1 collector is very similar that (it's a lot more complicated though).
Generational GC usually depends on write barriers to detect creation of references to newer generations inside older generations.
Immutability prevents the mutation of older generations, so no new references can occur.
So I expect generational GC to be easier to implement. I wouldn't expect it to be faster or slower though, because programs will need to be written differently to cope with the limitations on mutability. O(1) algorithms will likely be replaced by O(log(n)).
The actual GC of freeing memory is indeed possible (and common) without stop the world. Heap defrag is another story, though. This involves moving objects to different locations in memory, and if the memory is mutable, measures like stop the world is required since multi-byte move is not atomic.
Doesn't matter. In an immutable model, the old copy is guaranteed not to change, so you can safely copy it non-atomically. (That's one of the big benefits of immutability.)
Also you've just described existing GC systems - The Java G1 collector is very similar that (it's a lot more complicated though).