You only have to copy if your array is implemented as a simple linear sequence of memory addresses. More advanced implementations don't have to copy everything. E.g., Clojure's vectors (its array equivalent) are effectively O(1) for the common array operations that are O(1) on naive arrays, like indexing and insertion. But Clojure vectors are still purely functional. (The actual time for some of those ops is O(log32(n)), but log32(1,000,000) = 4, so it's effectively O(1).)

The term for this is "persistent data structures", usually implemented via trees, where replacing an object in a vector is implemented by building a new tree, reusing all of the old nodes except the ones that appear in the path from the root to the replaced node. That's why Clojure's Vector is log32; it's a 32 b-tree. (I'm writing this from memory and have little Clojure experience, but I'm pretty sure I have it right.)

Many languages have implementations now, but most aren't as fast as Clojure's. E.g., there's immutable.js: http://facebook.github.io/immutable-js/