Coded modulations with dense constellations can achieve high spectral efficiency, but the optimal receivers are often extremely complex, especially when the communication channel suffers from additional non-ideality, such as the inter-symbol interference (ISI) and fading. Thus practical designs resort to suboptimal schemes at a cost of reduced data rate. In this work, we propose a multilevel coding paradigm with low complexity and capacity-approaching performance for some channels with memory, specifically, the linear (nonlinear) ISI channels and the flat fading channels. The transmitter maps many levels of independently encoded binary data to generate the dense constellation for channel input. The receiver performs multistage decoding with decision feedback where at each stage, the linear or nonlinear equalization and channel estimation may be used depending on the channel type. For linear ISI channels and block fading channels, the complexity scales linearly with the channel length and the number of levels, and the process is shown to be asymptotically information lossless if a fixed input power is properly distributed over a sufficiently large number of layers. In addition, existing codes designed for memoryless channels can be applied directly. For nonlinear ISI channels, two nonlinear equalizers are introduced, the nonlinear ISI cancellation with linear complexity and the reduced-state BCJR algorithm with better performance and slightly higher complexity. Capacity analysis and code simulation results show that these two schemes can achieve significant improvement over the conventional approaches.