If by "group on exactly $n$ letters", you specifically mean the symmetric group $S_n$, then the answer is no, not in general. For example, see here - the Galois group of an irreducible cubic polynomial over $\mathbb{Q}$ will be $A_3\cong\mathbb{Z}/3\mathbb{Z}$ when its discriminant is the square of a rational number.
Also, the Fundamental Theorem of Algebra is really a consequence of topological properties of $\mathbb{R}$ and/or $\mathbb{C}$ - as is mentioned here, it is often remarked that it is not quite a theorem about algebra.
Reading your comments, I'm guessing perhaps you want "$G$ is a group on $n$ letters" to be synonymous with "$G$ can be viewed as a group of permutations of $n$ objects which acts transitively". If that is the case, then the Galois group of an separable irreducible polynomial of degree $n$ is always a group on $n$ letters, because the Galois group must indeed act transitively on the roots of the polynomial. If it didn't, we could break up the set of roots into the orbits of the action of the Galois group, and this would force the polynomial to factor - for example, if $f=\prod_{i=1}^n(x-\alpha_i)$, then if the Galois group permuted $\alpha_1,\ldots,\alpha_k$ amongst themselves, and permuted $\alpha_{k+1},\ldots,\alpha_n$ amongst themselves, then we could factor $f=gh$ where $g=\prod_{i=1}^k(x-\alpha_i)$ and $h=\prod_{i=k+1}^n(x-\alpha_i)$, and $g$ and $h$ are guaranteed to be polynomials over our base field because they are fixed by the action of the Galois group.
Also note that if a group $G$ acts transitively on a set of $n$ elements, then $|G|\geq n$, which also seems to coincide with what you are wanting the group to satisfy.