PUT to a non-existing resource should return 404.

RFC2616 §9.6 states
   "If the resource could not be created or modified with the
    Request-URI, an appropriate error response SHOULD be given
    that reflects the nature of the problem."

For me this should be a 404

I saw the comment in
https://github.com/clojure-liberator/liberator/issues/31

    "I think 404 would be the most appropriate when we can guarantee
     that there never will be created a resource at this URI via PUT.
     Else 405 or 409 might be more appropriate."

I don't think this is correct, we don't need to consider whether a resource might be created at this resource, the RFC says...

RFC2616 §10.4.5

   "The server has not found anything matching the Request-URI. No
    indication is given of whether the condition is temporary or
    permanent."