Correcting for Doppler shifts at the speed of sound for a 800 MHz signal
frequency shift of about 890 kHz (supposing my math is correct)


$$\begin{align}
\Delta f_\text{Doppler} &amp;= f_0 \frac vc\\
&amp;=800\cdot 10^6\,\text{Hz}\frac{3.4\cdot10^2\frac{\text m}{\text s}}{3\cdot 10^8\frac{\text m}{\text s}}\\
&amp;\approx 800\cdot 10^6\,\text{Hz}\cdot 1.13\cdot 10^{-6}\\
&amp;\approx 906 \,\text{Hz}
\end{align}$$

So, your shift expectation is off by a factor of 1000.


  Supposing we don't have to worry about interference, how should I go about correcting this frequency shift? I was thinking about using an FLL or a PLL, but I'm not sure where whether these could support such important shifts.


You can design the bandwidth of your PLL or FLL to accomodate any shift. It just gets a bit tricky keeping other signals out of the observation. 

Even your ~ MHz shift isn't all that much to deal with. Normal observers will simply have a  larger bandwidth than just necessary to observe your communication signal, anyways, and need


to have frequency correction anyways, since no two clocks / frequency generators are perfectly identical, physically (and if someone says "I've built this communication system. For now, I neglected synchronization needs", you know that they omitted the hard part)
When knowing what your communication signals look like, it's often not that hard to find them in the spectrum.
When you observe a communication partner for a while, you can easily write down a Doppler rate, i.e. the rate at which the Doppler shift changes. From that, you can predict future shifts and make your detection even easier (typical Kalman-Filter application)