See the last of this extended answer. I'm going to part company with everyone else and say that you can describe other elements of $\text{Gal}(\mathbb{Q})$. In other words, I claim that you can identity a specific element of $\text{Gal}(\mathbb{Q})$ in a wide range of ways, together with an algorithm to compute the values of that element as a function on $\mathbb{Q}$. You can use either a synthetic model of $\overline{\mathbb{Q}}$, or its model as a subfield of $\mathbb{C}$. Although this is all doable, what's not so clear is whether these explicit elements are interesting.
The other two parts of the answer raise interesting issues, but they are moot for the original question.
This is not exactly the question, but it is related. To begin with, it is difficult to "explicitly" describe $\overline{\mathbb{Q}}$ except as a subfield of $\mathbb{C}$. I found a paper, Algebraic consequences of the axiom of determinacy (in English translation of the title) that establishes that $\mathbb{C}$ does not have any automorphisms other than complex conjugation in ZF plus the axiom of determinacy (AD). So you need some part of the axiom of choice (AC) for this related question.
As for the smaller field $\overline{\mathbb{Q}}$, the Wikipedia page for the fundamental theorem of algebra suggests that you might not even be able to construct it in the first place without the axiom of countable choice. (I say "suggests" because I'm not entirely sure that that is a theorem. Note that AC and AD both imply countable choice even though they are enemy axioms.) Any construction with countable choice isn't truly "explicit". On the other hand, if you allow countable choice, then I suspect that you can build $\overline{\mathbb{Q}}$ synthetically by induction rather than as a subfield of $\mathbb{C}$, and that you can build many automorphisms of it as you go along.
So the questions for logicians is whether there is a universe over ZF in which $\overline{\mathbb{Q}}$ does not exist, or a universe in which it does exist but has no automorphisms.
I got email about this from Kevin Buzzard that made me look again at the paper referenced by Wikipedia, A weak countable choice principle by Bridges, Richman, and Schuster. According to this paper, life is pretty strange without countable choice. You want to make the real numbers as the metric completion of the rationals. However, there is a difference between general Cauchy sequences and what they called "modulated" sequences, which are sequences of rationals with a promised rate of convergence. They cite a result of Ruitenberg that the modulated complex numbers are algebraically closed in ZF. Hence $\mathbb{Q}$ has an algebraic closure in ZF.
But it still seems possible that without countable choice, algebraic closures of $\mathbb{Q}$ need not be unique up to isomorphism, and that the complex analysis model of $\overline{\mathbb{Q}}$ might not have automorphisms other than complex conjugation.
A better and hopefully final technical answer: As mentioned, $\overline{\mathbb{Q}}$ exists explicitly (in just ZF) as a subfield of $\mathbb{C}$. You can also construct it synthetically as follows: Consider the monic Galois polynomials over $\mathbb{Z}$. These are the polynomials such that the Galois group acts freely transitively on the roots; equivalently the splitting field is obtained by adjoining just one root. The Galois polynomials can be written in a finite notation and enumerated. Beginning with $\mathbb{Q}$, formally adjoin a root of $p_n(x)$, the $n$th monic Galois polynomial, for each $n$ in turn. If $p_n(x)$ factors over the field constructed so far, the factors can also be expressed in a finite notation; take the first irreducible factor. The result is an explicit, synthetically constructed $\overline{\mathbb{Q}}$.
For comparison, let $\widetilde{\mathbb{Q}}$ be the algebraic closure of $\mathbb{Q}$ in $\mathbb{C}$. Each element of it is computable: Its digits can be generated by an algorithm, even with an explicit bound on its running time. As we build $\overline{\mathbb{Q}}$, we can also build an isomorphism between $\widetilde{\mathbb{Q}}$. We can do this by sending the formal root of $p_n(x)$ to its first root in $\mathbb{C}$, using some convenient ordering on $\mathbb{C}$. Or we could just as well have used its last root, its second root if it has one, etc. Composing these many different isomorphisms between $\overline{\mathbb{Q}}$ and $\widetilde{\mathbb{Q}}$ gives you many field automorphisms.
Your requirements are quite stringent! As you know well, ANT is a couple of layers removed from "practice". In general, I find that the methods deriving from the development of algebraic number theory eventually lead to incomparably more applications than any of the standard ANT theorems themselves. Just a few examples that quickly spring to mind: Gauss reduction of quadratic forms → shortest lattice vectors → LLL; Dirichlet units → Minkowski geometry of numbers → convex geometry; class groups and unit groups → finitely generated abelian groups → (pick your favorite application of group theory, e.g. in abelian harmonic analysis). I would try to project this deeper idea over the immediate payoff. Also, unsurprisingly, "elementary" number theory presents more immediate applications, e.g. to cryptography and specifically, to primality testing and factorization.
But enough of philosophy! Here a few concrete applications:
Construction of codes and dense lattice packings using multiplicative groups of global fields by Rosenbloom and Tsfasman (Invent. Math. paper or see Tsfasman's survey "Global fields, codes and sphere packings").
Margulis arithmeticity theorem: not only are algebraic integers useful in constructing discrete groups, but after imposing certain conditions (an irreducible lattice in a higher rank semisimple Lie group), all of them arise in this way! These lattices have been used in constructing Ramanujan graphs and superconcentrators and to uniform distribution of points on spheres (admittedly, arithmetic of the field is rather secondary: you can get good constructions starting from a group over Z).
Lind's theorem on realizability of any Perron–Frobenius integer as the leading eigenvalues of a positive integer matrix. Since log λ is the entropy, this does have semi-practical consequences (cf the textbook of Lind and Marcus).
Lucas–Lehmer primality test, Lucas and Fibonacci pseudoprimes, Grantham's Frobenius test. This strides the border between elementary and algebraic number theory, which may actually be an advantage in an undergraduate class!
I'd be curious to know how do they jibe with your goals.
Best Answer
If you want to go further in understanding this point of view, I would advise you to begin learning class field theory. It is a deep subject, it can be understood in a vast variety of ways, from the very concrete and elementary to the very abstract, and although superficially it appears to be limited to describing abelian reciprocity laws, it in fact plays a crucial role in the study of non-abelian reciprocity laws as well.
The texts:
Ireland and Rosen for basic algebraic number theory, a Galois-theoretic proof of quadratic reciprocity, and other assorted attractions.
Cox's book on primes of the form x^2 + n y^2 for an indication of what some of the content of class field theory is in elementary terms, via many wonderful examples.
Serre's Local Fields for learning the Galois theory of local fields
Cassels and Frolich for learning global class field theory
The standard book at the graduate level to learn the arithmetic of non-abelian (at least 2-dimensional) reciprocity laws is Modular forms and Fermat's Last Theorem, a textbook on the proof by Taylor and Wiles of FLT. But it is at a higher level again.
I don't think that you will find a single text on this topic at a basic level (if basic means Course in arithmetic or Ireland and Rosen), because there is not much to say beyond what you stated in your question without getting into the theory of elliptic curves and/or the theory of modular forms and/or a serious discussion of class field theory.
Also, as basic suggests, you could talk to the grad students in your town, if not at your institution, then at the other one down the Charles river, which as you probably know is currently the world centre for research on non-abelian reciprocity laws (maybe shared with Paris). Certainly there are grad courses offered on this topic there on a regular basis.