I think you can avoid gensym here at all. I don't see how you can "pollute" environment by not using gensym. Example without gensym:
(defmacro def-handler [& addresses]
`(defn handler [~'request]
(case (~'request :uri)
~@(mapcat (fn[x] [(str "/" x) (list x 'request)]) addresses)
"/" (home ~'request)
(status-response 404 (str "<h1>404 Not Found: " (:uri ~'request) "</h1>" )))))