Differential unitary space-time modulation (DUSTM), which obtains full transmit diversity in slowly flat-fading channels without channel state information, has generated significant interests recently. To combat frequency-selective fading, DUSTM has been applied to each subcarrier of an OFDM system and DUSTM-OFDM system was proposed. Both DUSTM and DUSTM-OFDM, however, are designed for slowly fading channels and suffer performance deterioration in fast fading channels. In this paper, two novel differential unitary space-time modulation schemes are proposed for fast fading channels. For fast flat-fading channels, a sub-matrix interleaved DUSTM (SMI-DUSTM) scheme is proposed, in which matrix-segmentation and sub-matrix based interleaving are introduced into DUSTM system. For fast frequency-selective fading channels, a differential unitary space-frequency modulation (DUSFM) scheme is proposed, in which existing unitary space-time codes are employed across transmit antennas and OFDM subcarriers simultaneously and differential modulation is performed between two adjacent OFDM blocks. Compared with DUSTM and DUSTM-OFDM schemes, SMI-DUSTM and DUSFM-OFDM are more robust to fast channel fading with low decoding complexity, which is demonstrated by performance analysis and simulation results.