You can easily eliminate all references to complex numbers in a rather trivial way, although doing so results in much less mathematically elegant expressions. For example, you could choose to work in the position basis and, instead of using a complex-valued wavefunction that assigns a complex number to every point in configuration space, you could use a wavefunction with two real components, i.e. that assigns an ordered pair of real numbers $\vec{\psi}(\{\vec{x}_i\})$ to every point in configuration space. Multiplication by $i$ (e.g. in the Schrodinger equation and in the canonical commutation relations) would be replaced by an application of the orthogonal matrix
$$\hat{O} := \left( \begin{array}{cc} 0 & -1 \\ 1 & 0 \end{array}\right),$$ which rotates the "vector" $\vec{\psi}$ by 90 degrees counterclockwise. So the Schrodinger equation would become $\hat{H} \vec{\psi} = \hbar\, \hat{O}\, d\vec{\psi}/dt$ (in the position basis). But it would be much more complicated to do things like change basis.
In fact, this is exactly what all computational algorithms do "under the hood" - computers internally represent complex numbers as ordered pairs of real numbers, and all complex-number operations are converted into operations on pairs of reals.
Section 4 of this paper discusses some motivations for why we might expect that a theory like quantum mechanics might be most naturally expressed using complex numbers (which is very different from claiming that it can only be expressed using complex numbers). Basically, it would be nice if the field of numbers we use is algebraically closed. The square root of a complex number is always complex, but the square root of a real number isn't always real. However, the group $GL(2, \mathbb{R})$ of $2 \times 2$ real invertible matrices is algebraically closed, so that's just as good as the complex numbers in that sense. (Note for experts and nitpickers: I'm glossing over some subtleties here, like the fact that $GL(2, \mathbb{R})$ isn't closed under addition and therefore isn't a field, so strictly speaking you should be talking about closure under exponentiation rather than algebraic closure.)