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 = D_4 \times Q_8$ where $D_4$ is the eight-element dihedral group and $Q_8$ is the eight-element quaternion group. Famously, these have the same character table but are not isomorphic. Fixing a bijection between their conjugacy classes of these groups, and one of their characters, compatible with the character table, we obtain an automorphism of the character table of $D_4 \times Q_8$ - if $i$ is the isomorphism on conjugacy classes then we send the conjugacy class of $(a,b)$ to the conjugacy class of $(i^{-1}(b), i(a))$.
This character table automorphism cannot come from an outer automorphism (or Galois conjugation, since all character values are integers). If it did, the automorphism would send $D_4$ (a union of conjugacy classes) to $Q_8$ (the union of the images of those conjugacy classes) which i
This is part of a general tricks in mathematics that isomorphisms $A \to B$ with unusual properties often give automorphisms of $A\times B$ with unusual properties. This can be used as in this example to construct automorphisms, or in reverse, as in the proofs of the Tate conjecture for morphisms of abelian varieties which shows certain unusual homomorphisms between groups (the Tate modules of abelian varieties) cannot exist, by first using an unusual homomorphism to construct an unusual endomorphism and then showing that unusual endomorphims cannot exist.