I think the biggest piece of added complexity would be that String would need to be a lang item, giving the compiler special knowledge about it. Currently Vec and String are plain library types, so conceptually this would be a pretty big change.
I'm not familiar with Rust compiler internals (I am familiar with other compilers though), but there are many ways to implement this, which could happen in a stage before types are considered (for example the expression `"Hello {a + b}"` could be first internally transformed to `format!("Hello {}", a + b")` - more complexity ensues, but it is doable).
I think the biggest piece of added complexity would be that String would need to be a lang item, giving the compiler special knowledge about it. Currently Vec and String are plain library types, so conceptually this would be a pretty big change.