I'd like to start learning Lisp as it sometimes leads to interesting answers on this site with concepts borrowed from this language, so I'm curious. As I already spend most of my programming time in Mathematica, is there a way to execute Lisp programs from the Mathematica frontend?
Have a look at SchemeLink.
Clojure is often described as a "modern-day LISP" (hosted on the JVM) that offers strong support for multi-threaded code.
If the Clojure dialect of LISP is an option for you then you might want to investigate using the JLink-based interface to Clojure provided courtesy of this package: Clojuratica
Regarding Haskell and OCaml, your best bet may be trying to access F# (which is closely related to Haskell and OCaml) through .NETLink.
I haven't actually tried this, but you might want to investigate using one of the Lisps for the JVM, such as Armed Bear Common Lisp, and interface to Mathematica through J/Link.
These pages contain related links about a lisp interpreter in Mathematica: