Would it be feasible to implement Clojure (and persistent data structures) on EVM? Or another functional language?
Sure you'd need to create your compiler to generate EVM bytecode. There are alternatives to solidity, they are LLL (which is functional and Lisp like) https://github.com/nexusdev/lll-resurrected
and Serpent which looks more like a Python. https://github.com/ethereum/wiki/wiki/Serpent
Assumed you generate a proper bytecode and an ABI, I guess you can use almost any language to write contracts.