The ever-increasing number of wireless users (or devices) and their varied demand require the need for an advanced architecture for the future wireless network. To support massive connectivity, non-orthogonal multiple access (NOMA) has been recognized as a promising solution. NOMA increases the number of simultaneous connections using available resources for users with varying demands. Furthermore, recent measurements and experiments suggest that wide underutilized bandwidth available at millimeter-wave (mmWave) frequencies provide high data rate and therefore are capable of addressing the issue of spectrum scarcity at sub-6 GHz bands utilized by the 4 G network. Consequently, co-existence of multi-radio access technologies (RATs) for 5 G and beyond networks has been of interest to both industries and academia. In this context, this work studies the co-existence of the two RATs, namely, sub-6 GHz and mmWave communication using NOMA-enabled hybrid heterogeneous network (NOMA-HHN) for massive connectivity. The application of NOMA requires ordering users, which in turn requires the knowledge of users' channel state information (CSI). However, gathering and processing CSI of such a large number of users is difficult to implement in practice. Thus, a solution based on partial CSI is proposed. Additionally, a feedback scheme for user scheduling and RAT selection using dual association is proposed to reduce the initial access delay in beam-training at the mmWave network. Moreover, utilizing directional nature of the mmWave communication, random beamforming is used to reduce system overhead in a network with massive users. The analytical results are confirmed using Monte-Carlo simulation, and various significant advantages are noted for the proposed NOMA-HHN over existing architectures.