In this paper, we develop a joint channel estimation and decoding method for faster-than-Nyquist signaling (FTNS) transmitting over (quasi-static) time-varying frequency-selective fading channels based on the variational Bayesian (VB) framework. In contrast to existing methods, ours is capable of performing explicit frequency-domain channel estimation and decoding in a turbo mode without requiring any cyclic prefix (CP), as well preserving the computational complexity at a logarithmic level. In view of the colored noise inherent in FTNS, we propose to approximate the corresponding autocorrelation matrix by a circulant matrix, the special eigenvalue decomposition of which facilitates an efficient fast Fourier transform operation and decoupling the noise in frequency domain. In addition, through a specific partition of the received symbols, many independent estimates are obtained and combined to further improve the accuracy of the channel estimation and data detection. Simulation results show that the proposed algorithm outperforms the conventional CP-based and overlap-based frequency-domain equalization methods with known channel impulse response (CIR). Moreover, ours come within $1$dB of the counterpart Nyquist system with 25% higher spectral efficiency achieved when the CIR is unknown.