The requirements to support massive connectivity and low latency in massive Machine Type Communications (mMTC) bring a huge challenge in the design of its random access (RA) procedure, which usually calls for efficient joint active user detection and channel estimation. In this paper, we exploit the vast sequence space and the beneficial nested structure of the length-$2^m$ second-order Reed-Muller (RM) sequences for designing an efficient RA scheme, which is capable of reliably detecting multiple active users from the set of unknown potential users with a size as large as $2^{m(m-1)/2}$, whilst simultaneously estimating their channel state information as well. Explicitly, at the transmitter each user is mapped to a specially designed RM sequence, which facilitates reliable joint sequence detection and channel estimation based on a single transmission event. To elaborate, as a first step, at the receiver we exploit the elegant nested structure of the RM sequences using a layer-by-layer RM detection algorithm for the single-user (single-sequence) scenario. Then an iterative RM detection and channel estimation algorithm is conceived for the multi-user (multi-sequence) scenario. As a benefit of the information exchange between the RM sequence detector and channel estimator, a compelling performance vs. complexity trade-off is struck, as evidenced both by our analytical and numerical results.