We propose iterative, adaptive trellis-based blind sequence estimators, which can be interpreted as reduced-complexity receivers derived from the joint ML data/channel estimation problem. The number of states in the trellis is considered as a design parameter, providing a trade-off between performance and complexity. For symmetrical signal constellations, differential encoding or generalizations thereof are necessary to combat the phase ambiguity. At the receiver, the structure of the super-trellis (representing differential encoding and intersymbol interference) is explicitly exploited rather than doing differential decoding just for resolving the problem of phase ambiguity. In uncoded systems, it is shown that the data sequence can only be determined up to an unknown shift index. This shift ambiguity can be resolved by taking an outer channel encoder into account. The average magnitude of the soft outputs from the corresponding channel decoder is exploited to identify the shift index. For frequency-hopping systems over fading channels, a double serially concatenated scheme is proposed, where the inner code is applied to combat the shift ambiguity and the outer code provides time diversity in conjunction with an interburst interleaver.