In this work, Generalized Space-Time Super-Modulation (GSTSM) is introduced which enables the transmission of an additional flexible-rate and highly-reliable information stream concurrently with the conventionally transmitted symbols, without the need for increasing the corresponding packet length. This is attained by jointly exploiting the spatial and temporal dimensions of multiple-antenna systems, which enables efficient detection for conventional and additional information subchannels even in highly correlated channel conditions or AWGN channels. In the context of machine-type communications, GSTSM enables grant-free medium access without transmitting additional headers to convey each machine's signature information. Hence, it is shown that even at an extreme case where the data packets of two users are always colliding, GSTSM offers throughput gains of up to 33% compared to the best examined header-based scheme. For the same scenario, it is shown that GSTSM based on joint multi-user detection provides throughput gains of up to 2.5times compared with the case where users' signals are detected independently. In addition, it yields over 90% improvement in achievable rates compared with the schemes that require centralized medium-access coordination. For both joint and independent signal detection schemes, it is also shown that adopting an iterative detection/decoding approach allows to further improve the throughput gains.