OK, I've thought about it a bit more and I'll give an alternate proof below the first horizontal line. However, I highly deny that this proof is better, and I am not sure it is actually shorter.
To my mind, the morally correct proof is to show that, if $K \subseteq L$ with $L$ algebraically closed, and a system of polynomial equations has a root in $L$, then it has a root in a finite extension of $K$.
The point, which I am sure Qiaochu understands, is that he only knows a priori that the representation is defined over $\mathbb{C}$. Once he knows that the representation is definable over an algebraic extension $K'$ of $K$, he can replace $K'$ by its normal closure, note that $\mathrm{Gal}(K', \mathbb{Q}) \to \mathrm{Gal}(K, \mathbb{Q})$ is surjective, lift any element $\sigma$ of $\mathrm{Gal}(K, \mathbb{Q})$ to some $\tilde{\sigma}$ in $\mathrm{Gal}(K', \mathbb{Q})$, and apply $\tilde{\sigma}$ to the entries of his matrices.
Part of the problem is that the representation may honestly not be defined over $K$. For example, the two dimensional representation of the quaternion eight group has character with values in $\mathbb{Q}$, but can't be defined over $\mathbb{Q}$.
Fix $G$ and a representation $V$ of $G$. For $g \in G$, let $\lambda_1(g)$, $\lambda_2(g)$, ..., $\lambda_n(g)$ be the multiset of eigenvalues of $g$ acting on $V$. These are necessarily roots of unity, since $g^N=1$ for some $N$. For any symmetric polynomial $f$, with integer coefficients, define $\chi(f,g) = f(\lambda_1(g), \ldots, \lambda_n(g))$.
Lemma: With notation as above, $g \mapsto \chi(f,g)$ is a virtual character.
Proof: If $f$ is the elementary symmetric function $e_k$, then this is the character of $\bigwedge^k V$. Any symmetric function is a polynomial (with integer coefficients) in the $e_k$'s; take the corresponding tensor product and formal difference of virtual characters.
Any Galois symmetry $\sigma$ of $\mathbb{Q}(\zeta_N)$ is of the form $\zeta_N \mapsto \zeta_N^s$, for $s$ relatively prime to $N$. Consider the power sum symmetric function $p_s := \sum x_i^s$. So $\chi(p_s, \ )$ is the Galois conjugate $\chi^{\sigma}$, and we now know that it is a virtual character.
But $\langle \chi^{\sigma}, \chi^{\sigma} \rangle = \langle \chi, \chi \rangle =1$, because the inner product is built out of polynomial operations and complex conjugation, and complex conjugation is central in the Galois group. So this virtual character must correspond to $\pm W$, for some representation $W$. Since $\chi^{\sigma}(e) = \chi(e) = \dim V$, we conclude that the positive sign is correct.
It just occurred to me that actually writing this out for some specific small values of $s$ makes some nonobvious statements about representation theory. For example, if $G$ has odd order and $V$ is a $G$-irrep, then $\bigwedge^2 V$ has a $G$-equivariant injection into $\mathrm{Sym}^2 V$. Proof: The difference of their characters is the character of $V^{\sigma}$, where $\sigma: \zeta \mapsto \zeta^2$.
Since you have the [gap] tag: In GAP you could construct the group, calculate the automorphism group, and then its character table. Say, for $SL(2,9)$:
gap> g:=PerfectGroup(720,1);
A6 2^1
gap> IsomorphismGroups(g,SL(2,9))<>fail; # verify its the right one
true
gap> a:=AutomorphismGroup(g);
<group of size 1440 with 4 generators>
gap> p:=Image(IsomorphismPermGroup(a),a); # convert to permutation (since faster)
<permutation group of size 1440 with 4 generators>
gap> c:=CharacterTable(p);
CharacterTable( <permutation group of size 1440 with 4 generators> )
gap> Irr(c);; # completes character calculation
gap> Display(c); # show table
CT1
2 5 5 4 3 3 1 4 3 4 1 1 3 1
3 2 . . . . . . . 1 2 1 . .
5 1 . . . 1 1 . . . . . . 1
1a 2a 4a 4b 2b 5a 4c 8a 2c 3a 6a 8b 10a
2P 1a 1a 2a 2a 1a 5a 2a 4c 1a 3a 3a 4c 5a
3P 1a 2a 4a 4b 2b 5a 4c 8a 2c 1a 2c 8b 10a
5P 1a 2a 4a 4b 2b 1a 4c 8a 2c 3a 6a 8b 2b
7P 1a 2a 4a 4b 2b 5a 4c 8a 2c 3a 6a 8b 10a
X.1 1 1 1 1 1 1 1 1 1 1 1 1 1
X.2 1 1 -1 -1 1 1 1 1 -1 1 -1 -1 1
X.3 1 1 -1 1 -1 1 1 -1 -1 1 -1 1 -1
X.4 1 1 1 -1 -1 1 1 -1 1 1 1 -1 -1
X.5 9 1 -1 -1 1 -1 1 -1 3 . . 1 1
X.6 9 1 -1 1 -1 -1 1 1 3 . . -1 -1
X.7 9 1 1 -1 -1 -1 1 1 -3 . . 1 -1
X.8 9 1 1 1 1 -1 1 -1 -3 . . -1 1
X.9 10 2 2 . . . -2 . 2 1 -1 . .
X.10 10 2 -2 . . . -2 . -2 1 1 . .
X.11 16 . . . -4 1 . . . -2 . . 1
X.12 16 . . . 4 1 . . . -2 . . -1
X.13 20 -4 . . . . . . . 2 . . .
Best Answer
Take $G = S_3 \times S_4$ and consider the unique two-dimensional irreducible representation of $S_3$ and the unique two-dimensional irreducible representation of $S_4$. These have the same character values $2,0,-1$ (in fact they are both pullbacks of the same representation under two different homomorphisms $S_4 \to S_3$ ) but are not related by any combination of the operations.
Galois conjugation is irrelevant since the characters are rational. Twisting by one-dimensional characters can only twist by quadratic characters and doesn't affect the value on order $3$ elements - i.e. $3$-cycles in $S_3$, $3$-cycles in $S_4$, or products of $3$-cycles in both $S_3$ and $S_4$. So it remains to consider outer automorphisms, which would have to permute these three conjugacy classes. But no outer automorphism can since their centralizers have different orders: $3 \cdot 24, 6 \cdot 3,$ and $3 \cdot 3$ respectively.