Is there a geometric realization of Quaternion group?
Solution 1:
Consider the symmetries of a set of three copies of $[-1,1]$ positioned orthogonally with each other, all intersecting at the 0 element. (This is kind of the three dimensional analogue of the cross you mentioned.) Identify the positive rays on each of these axes with $i$ $j$ and $k$ as is usually done in vector algebra, and the negative counterparts with $-i$, $-j$ and $-k$, as usual.
Each member of the quaternion group is a symmetry of this shape when it acts by conjugation. Conjugating by $i$ produces a half-turn of the shape around the $i$ axis, and analogous statements hold for the $j$ and $k$ axes.
These are not all symmetries of the shape, because there is no way to get a quarter turn. Thus, we need to alter the cross shape by painting the axes three different colors. That would prevent quarter turns from being counted as symmetries.
There is a well-known obstacle, though, that each rotation is represented by two quaternions in this conjugation action. The issue is that conjugating by $i$ and conjugating by $-i$ produces the same symmetry, and of course, the same thing can be said for other elements...)
One gets the feeling that we have to pay a price for painting our axes :)
Edit: As I think about it, I think this must be surmountable in the same way that one can visualize the quaternions representing all symmetries of the sphere in 3-space. This is just a discrete subcase.
I'm tempted to analogize with the full case by using two such crosses with some of the ends identified, but I wonder if there is a simpler setup by considering the cross with a ray. The modified action would be that quaternion group elements are distinguished from their negative counterparts by their action on the ray. If the element has a negative sign in front, it flips the ray from pointing up to pointing down. If it does not have a negative sign in front, the ray remains pointing upward.
Added: The ray is not as appealing as having two crosses, but I think it is easier to visualize. If I wanted to describe the two cross picture, I would first start off with a 2-d analogue.
Take two crosses with two axes, where each pair has one red axis and one blue axis. Now you lay them back to back so that colors are aligned. If the element of the group were of "negative" type, then you would rotate the bottom cross a half-turn, and if it is of positive type, rotate the top cross a half-turn. This is difficult to imagine for two 3-d crosses, but I think it is a valid workaround for the unfaithfulness of the cross representation.
This is right along the lines of a twisty-puzzle that you mentioned! However, twisty puzzles for dimensions over 3 are hard to visualize...
Solution 2:
Applying Cayley's theorem we can represent $Q_8$ as a group of permutations on $8$ symbols:
$$\begin{array}{|ccc|} \hline 1 & i & j \\ \hline -1 & -i & -j \\ \hline i & -1 & -k \\ \hline j & k & -1 \\ \hline k & -j & i \\ \hline -i & 1 & k \\ \hline -j & -k & 1 \\ \hline -k & j & -i \\ \hline \end{array}$$
Then the group is generated by
$$i = (1\;i\;\bar 1\;\bar i)(j\;k\;\bar j\;\bar k)$$
and
$$j = (1\;j\;\bar 1\;\bar j)(i\; \bar k\;\bar i\;k),$$
for completeness
$$k = (1\;k\;\bar 1\;\bar k)(i\;j\;\bar i\;\bar j)$$
So here is a labelling of the vertices of a cube and the action of $\color{red}i,\color{green}j,\color{blue}k$ on it:
A problem is that we can't twist these without making vertices pass through each other.