How can I Move a Document to Another Location Without Having to Create a New Version?

The following video will walk you through the steps of changing a folder location for a document:

To change the location of a document, without having to create a new version (with all that it involves), you can simply use the Change Location item from Document Actions submenu when viewing the document.

From there, pick the new location and confirm. 

The document will immediately be moved to the new location.