Is there a geometric realization of Quaternion group? Is there a geometric realization of the Quaternion group:
$$Q = \langle i,j,k \mid i^2 = j^2 = k^2 = ijk \rangle$$
I dont think it can be realized as the symmetries/rotations of a 3D shape so could we realize it as a kind of twisty-puzzle or something?

Just because it was so difficult, let me add how to show Q finite: starting with $i^2=j^2=k^2=ijk$ we get $i=jk$ and $k=ij$ by cancelling, together that gives $i=jij$ squaring $j^2=i^2=jij^2ij=ji^4j$ so $1=i^4$.
 A: 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...
A: 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.
A: Think of a geometric realization of the Dihedral group $D_4$ as the symmetries of a square. You can view these symmetries and thus $D_4$ as a set of orientation preserving rotations of $\mathbb{R}^3$. This says you should think of $D_4\subset SO(3)$ as a finite subgroup. Now the unit Quaternions i.e., $S^3$, is  the (universal) double cover of $SO(3)$. Let $\pi: S^3\rightarrow SO(3)$ be the projection map. The group you're interested in is $Q_8 = \pi^{-1}(D_4)$. Combine your geometric understanding of $D_4$ with your geometric understanding of $\pi$ to get the interpretation you're looking for. 
A: In 2014 (a year after this question was posted), Vi Hart and Harry Segerman released the very nice paper The quaternion group as a symmetry group, answering it.  This paper presents a 4-dimensional object whose symmetries are precisely $Q_8$. Specifically, it’s a certain decoration on a hypercube; unfortunately it is somewhat intricate to describe, but good descriptions/illustrations can be found in that paper.  Here is one as a taster:

