Suppressing the inter-carrier interference (ICI) is crucial for differentially coherent detection in underwater acoustic (UWA) orthogonal frequency division multiplexing (OFDM) systems due to the fact that the UWA channel is inherently violently Doppler-shifted. In this paper, we propose a new ICI suppression method, referred to as the partially-shifted fast Fourier transform (PS-FFT), which eliminates the ICI from both the time and frequency domains. Specifically, the PS-FFT first divides the received signal in the entire block duration into several short non-overlapping ones to reduce the channel variation in the time domain. It then applies the Fourier transform at several predefined frequencies to the received signal in each of these intervals to compensate Doppler shifts in the frequency domain. Finally, it weightedly combines the multiple demodulator outputs at each carrier as one output for symbol detection, with the combiner weights being solved by the stochastic gradient algorithm. Simulation results show that the PS-FFT dramatically outperforms the existing classical methods, the partial fast Fourier transform (P-FFT) and the fractional fast Fourier transform (F-FFT), for both medium and high Doppler factors and large carrier numbers in terms of the mean squared error (MSE). Numerically, the MSE of the PS-FFT is reduced by $\bf{61.83\%-84.89\%}$ compared to that of the F-FFT when the input signal-to-noise ratio (SNR) at the receiver ranges from 10 dB to 30 dB at a Doppler factor of $\bf{3\times 10^{-4}}$ and a carrier number of 1024 where the P-FFT even cannot work.