I think there are degrees of this.
Like, once you have
* first class functions that you can pass around
* anonymous functions
* closures over functions
you can get by. This is what enables you to create the usual higher-order function toolbox, all those nice functions that convert your code to long list of composable map/filter/reduce/zip/walk e.t.c.
I remember reading that python got here iteratively, i.e. you could pass around functions, but they needed to be defined top-level, then you had anonymous functions, but you needed to pass in variables from enclosing scope explicitly, and finally you had closures.
But I agree that fast, immutable datastructures make all of this much nicer. But not having them is not as much of a deal-breaker.
Similarily tail-call optimization. I used clojure at work while dealing with haskell on a school projects, and from that time on, I found "loop/recur" kinda ugly :-) NodeJS with --harmony actually supports it now.
Similarly, pattern matching. Don't you need to pull that as a lib in clojure as well? With destructuring this almost is a js feature.
So, I wouldn't loose much sleep over it anyway :)