Cellular machine-to-machine (M2M) communication can be one of the 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 the RA procedure and non-orthogonally allocate physical uplink shared channel resources at the second step of the 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.