Given the requirements of increased data rate and massive connectivity in the Internet-of-things (IoT) applications of the fifth-generation communication systems (5G), non-orthogonal multiple access (NOMA) was shown to be capable of supporting more users than OMA. As a further potential enhancement, the faster-than-Nyquist (FTN) signaling is also capable of increasing the symbol rate. Since NOMA and FTN signaling impose non-orthogonalities from different perspectives, it is possible to achieve further increased spectral efficiency by exploiting both. Hence we investigate the FTN-NOMA uplink in the context of random access. Although random access schemes reduce the signaling overheads as well as latency, they require the base station to identify active users before performing data detection. As both inter-symbol and inter-user interferences exist, performing optimal detection requires a prohibitively high complexity. Moreover, in typical mobile communication environments, the channel envelope of users fluctuates violently, which imposes challenges on the receiver design. To tackle this problem, we propose a joint user activity tracking and data detection algorithm based on the factor graph framework, which relies on a sophisticated amalgam of expectation maximization (EM) and hybrid message passing algorithms. The complexity of the algorithm advocated only increases linearly with the number of active users. Our simulation results show that the proposed algorithm is effective in tracking user activity and detecting data symbols in dynamic random access systems.