Under high mobility, the orthogonality between sub-carriers in an OFDM symbol is destroyed resulting in severe inter-carrier interference (ICI). We present a novel algorithm to estimate the channel and ICI coefficients by exploiting the channel's time and frequency correlations and the (approximately) banded structure of the frequency-domain channel matrix. In addition, we invoke the asymptotic equivalence of Toeplitz and circulant matrices to reduce the dimensionality of the channel estimation problem by retaining the dominant terms only in an offline eigen-decomposition. Furthermore, we show that the asymptotically MMSE-optimum pilot design consists of identical equally-spaced frequency-domain clusters whose size is determined by the channel Doppler spread. Comparisons of our proposed algorithm with a widely-cited recent algorithm demonstrate a significant performance advantage at a comparable real-time complexity.