Permutations of maximum period: applications to Rubik's cube
Copy/paste from another (slightly different) cstheory question on Rubik's cube:

"What is the shortest sequence that scans all cube's configurations", or "does the configuration graph of the cube have a Hamiltonian path?" is a special case of a more general unsolved problem: 

For an arbitrary permutation group with a given generating set, is its Cayley graph Hamiltonian?

There are some good info available online, you can download the lecture notes by W.D.Joyner: Mathematics of the Rubik's cube (downloadable in pdf format).

Chapter 6 of the lecture notes is devoted to Cayley graphs and God's algorithm.

EDIT: If I correctly interpret the question "Does such a permutation even exist?", the answer is yes (the Cayley graph of a finite group is connected); a trivial argument:


let $k$ be the total number of wrong configurations;
for every wrong configuration $W_i, 1 \leq i \leq k$ write down the solving sequence of moves $S_i$;
let $S_i^{-1}$ be the inverse sequence of $S_i$;
obviously the (long) sequence $S_1 \cdot S_1^{-1} \cdot S_2 \cdot S_2^{-1} ... \cdot S_{k-1}^{-1} \cdot S_{k-1}^{-1} \cdot S_k$ will lead you to the solved configuration from any wrong starting configuration, but you must "look at the cube" to see when to stop (there is no "synchronizing sequence").