Look also at CLUSTER (http://www.postgresql.org/docs/9.4/static/sql-cluster.html). Unlike VACUUM FULL, CLUSTER *does* write the data to a new disk files but is far faster than VACUUM and can reorder the table data to match an index which can improve the performance of certain queries. CLUSTER requires sufficient available disk-space to write the new copy of the table and associate indexes which can be anywhere from the size of your original table/indexes if it is already packed to far less if the table is heavily bloated.
N.B. The operation of CLUSTER and VACUUM have changed from version to version so read the docs for your version.
This information seems a little off. It was true that VACUUM FULL did not rewrite the table, but that has been changed since version 9.0 [1]:
"New implementation of VACUUM FULL. This command now rewrites the entire table and indexes, rather than moving individual rows to compact space. It is substantially faster in most cases, and no longer results in index bloat."
So, it was common to use CLUSTER instead of VACUUM FULL before 9.0, but since then CLUSTER is needed only if you really want to enforce the the order.
For example, CLUSTER used to require an index and would reorder using that index. This requirement has been dropped in the latest version.
No, at least up to 9.4 (the latest version today), CLUSTER still requires an index, the command itself does not, but only in case that there is a previously clustered index for the table.