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

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.