How do $\theta$-terms not violate gauge invariance? In the context of QCD (and more generally, any quantum gauge theory in even dimensions), the $\theta$-term is
$$
\frac{\theta}{8\pi^2}\langle F_A\wedge F_A\rangle = \frac{\theta}{32\pi^2}\langle F_A^{\mu\nu}, F_A^{\rho\sigma}\rangle\epsilon_{\mu\nu\rho\sigma}
$$
and its integral over spacetime is not exactly gauge invariant—instead it transforms under a general gauge as
$$
\int\frac{\theta}{8\pi^2}\langle F_A\wedge F_A\rangle
\overset{g}{\mapsto}
\int\frac{\theta}{8\pi^2}\langle F_A\wedge F_A\rangle + \theta n_g
\tag{1}\label{1}
$$
where $n_g \in \mathbb Z$ is the winding number of the gauge transformation $g$ (Ref. Tong’s lecture notes, §2.2). (Edit: I think I am confused—\eqref{1} may be wrong.)
(Bonus question: what does \eqref{1} look like with $\hbar$ not set to unity?)
Ultimately, physical predictions are made with the partition function or ‘quantum-mechanical amplitude’ given by the path-integral
$$
\mathscr A = \int_{\partial\Omega}\! \mathcal D[\psi, A] \exp\left(\frac{i}{\hbar} \int_{\Omega}\! \mathcal L\left[\psi, \nabla_{\!A}\psi, F_A\right]\right)
.$$
This is an integral over all gauge field configurations $A$. However, it appears that two physically equivalent gauge field configurations $A$ and $A^g$ separated by a ‘large’ gauge transformation $g$ would contribute differently to the partition function: $A$ contributes $\exp(\frac{i}{\hbar}\int\mathcal L)$ while $A^g$ contributes $\exp(\frac{i}{\hbar}\int\mathcal L)\exp(i\theta n_g)$, which appear to differ by a phase.
Doesn’t this make $\mathscr A$ ill-defined, unless $\theta \in 2\pi\mathbb{Z}$? How does the $\theta$ term not spoil gauge invariance in this sense?
Note: I think I might be confusing “the integral of the $\theta$-term is discrete over instanton configurations” with “the $\theta$-term is gauge invariant modulo a discrete additive factor”. Are both of these accurate?
 A: $\newcommand{\D}{\mathrm{D}}\newcommand{\Tr}{\mathrm{Tr}}$
In the usual treatment, $\theta$ is a coupling constant, i.e. a fixed parameter and not a field. Therefore shifting $\theta$ to $\theta' \color{gray}{(\neq \theta+2\pi n, \ n\in\mathbb{Z})}$ definitely changes the physics. Your question is equivalent to asking whether changing the parameters of a potential changes the physics or not; the answer of course is that it changes the physics. Changing $\theta\mapsto\theta'$ is totally unrelated to the gauge transformation $A\mapsto A^g$. As @MannyC correctly pointed out in a comment, the $\theta$-term is exactly gauge invariant under $A\mapsto A^g$.
What you probably had in mind is the observation that $\theta\mapsto\theta+2\pi$ does indeed leave the partition function (what you call the quantum-mechanical amplitude) invariant
$$Z[\theta+2\pi] = Z[\theta],\tag{1} $$
which is essentially because the second Chern class is integral
$$\int c_2(F) = \frac{1}{4\pi^2}\int \Tr(F_A\wedge F_A) \in \mathbb{Z}.$$

For a more modern treatment, that goes beyond your question, but is very cool one may wonder whether there is a gauge principle behind (1), I.e. can I consider $\theta$ as a gauge field for some kind of symmetry? 
The answer is in fact yes. Using what's known as higher-form symmetries [1], one finds that the gauge field for a $p$-form symmetry is a $(p+1)$-form connection. So the case $p=0$ corresponds to the normal 1-form connections $A$ that you know of, that transform under normal gauge transformations. Putting $p=-1$ we have a $(-1)$-form symmetry whose gauge field is a $0$-form, i.e. a scalar. Then you can think of $\theta$ as a gauge field and $\theta+2\pi\sim\theta$ as a gauge transformation for the gauge group $\mathbb{Z}$, yielding another explanation to why (1) holds. 

References
[1] D. Gaiotto, A. Kapustin, N. Seiberg, B. Willet, Generalized global symmetries, arXiv:1412.5148
