Is it possible to "unshift" onto a queue using this theoretical "queue automaton"?
Without any way of creating an unmistakeable marker on the tape, this is not possible. (As far as I recall (cannot check right now), the tape in Manufactoria is actually bounded, which would make a difference, but let us assume this is not the case.)

Let $i$ be any input string, and consider the computation of a given automaton on $i$, i.e. the sequence $(s_0,x_0),\dots,(s_n,x_n)$ with $s_0=sInit$, $x_0=i$, $s_n=sTerm$, and $(s_{j+1},x_{j+1}) = step((s_j,x_j))$. In iteration $j$, we read and remove the first letter $a_j$ of $x_{j-1}$ and append a word $u_j$; these first letters form a word $w=a_1\dots a_n$. 

It is not hard to see that any input word which starts with $w$, i.e. $wv$ for some $v$, is indistinguishable from $i$ to our automaton: it reads the same letters as it would on $i$, and as a result goes through the same states and appends the same $u_j$, so that the resulting word at the end is $vu_1\dots u_n$. This will fail to have the required form for any $v$ not starting with $G$ (and many others as well).