First of all, there's nothing wrong with readable URIs and with users being able to easily explore your API by building URIs by hand. As long as they are not using that to drive the actual API usage, that's not a problem at all, and even encouraged by Roy Fielding himself. Disagreement on that on the basis that URIs must be opaque is a myth. Quoting Fielding himself on that matter:
Maybe I am missing something, but since several people have said that REST implies opaqueness in the URI, my guess is that a legend has somehow begun and I need to put it to rest (no pun intended).
REST does not require that a URI be opaque. The only place where the word opaque occurs in my dissertation is where I complain about the opaqueness of cookies. In fact, RESTful applications are, at all times,
encouraged to use human-meaningful, hierarchical identifiers in order to maximize the serendipitous use of the information beyond what is anticipated by the original application.
It is still necessary for the server to construct the URIs and for the client to initially discover those URIs via hypertext responses, either in the normal course of creating the resource or by some form of query
that results in a hypertext list. However, once that list is provided, people can and do anticipate the names of other/future resources in that name space, just as I would often directly type URIs into the
location bar rather than go through some poorly designed interactive multi-page interface for stock charts.
http://osdir.com/ml/web.services.rest/2003-01/msg00074.html
If you need your client developers to follow the hyperlinks and not build URIs by hand, from my experience I think the best way to do that is to promote it as a cultural change in your work environment. In my case I had a supportive manager, so it was much easier. You should warn them that the URI namespace is under control of the server and the URIs may change anytime. If their clients break because they failed to comply, it's not your responsibility. It also helps a lot to have some sort of workshop or presentation to explain how HATEOAS works and the benefits for everyone. I noticed how a lot of street-REST developers think it's superfluous, until they actually get it.
Now, to address your main question, you shouldn't document the API, you should focus your documentation efforts on your media-type. Quoting Fielding again:
A REST API should spend almost all of its descriptive effort in defining the media type(s) used for representing resources and driving application state, or in defining extended relation names and/or hypertext-enabled mark-up for existing standard media types. Any effort spent describing what methods to use on what URIs of interest should be entirely defined within the scope of the processing rules for a media type (and, in most cases, already defined by existing media types). [Failure here implies that out-of-band information is driving interaction instead of hypertext.]
http://roy.gbiv.com/untangled/2008/rest-apis-must-be-hypertext-driven
That means, you should have custom media-types for your representations, and instead of documenting API endpoints or URIs, you should document those media-types and the operations for the links available in them. For instance, let's say you have an API for a Q&A site like StackOverflow. Instead of having an API documentation telling them that they should POST to the rel:answers link in the representation of a question in order to answer it with their current user, your questions should have a media-type of application/vnd.yourcompany.question+xml and on the documentation for that media-type you say that a POST to a rel:answers http link will answer the question.
I don't know of any existing tools for this, but from my experience, any tool that can be used to generate documentation from abstract models can be used for this.
I don't know how your ecosystem of APIs is, but what works for me is to have a generic documentation with a gentle introduction to REST, addressing some of the misconceptions, and detailed general usage to your patterns, that should apply to any API. After that, each individual server should have its own documentation, focused on the media-type.
I don't like the idea of returning documentation in the text/html representation, because that's supposed to represent the resource itself, but I love the idea of having a rel:doc link pointing to your HTML documentation for that media-type.
