Cellular machine-to-machine (M2M) communication can be one of major candidate technologies to develop an Internet of Things (IoT) platform. A massive number of machine nodes access the cellular networks and typically send/receive small-sized data. In this situation, severe random access (RA) overload and radio resource shortage problems may occur if there is no evolution in the conventional cellular system. Focusing on RA, we need a larger number of preambles as well as a more efficient resource allocation scheme in order to accommodate a significantly large number of RA requests from machine nodes. In this paper, we propose a non-orthogonal resource allocation (NORA) scheme combined with our spatial group based RA (SGRA) mechanism in order to provide a sufficiently large number of preambles at the first step of RA procedure and nonorthogonally allocate physical uplink shared channel (PUSCH) resources at the second step of RA procedure. As a result, the proposed SGRA-NORA scheme can significantly increase the RA success probability, compared with that of the conventional RA scheme.