Efficient connectivity in cellular-connected unmanned aerial vehicles (UAV)s is limited by scarcity of the radio spectrum and strong inter-cell interference (ICI). To address these issues, we propose an aerial-terrestrial network non-orthogonal multiple access (ATN-NOMA) scheme. In this proposed scheme, we pair the aerial user (AU) and terrestrial user (TU) in a NOMA setting to leverage their asymmetric channel gains and rate demands in downlink communications. In ATN-NOMA, the strong ICI issue at the AU receiver is further managed by an elevation-angle based user association, equipping the AU with an adjustable beamwidth directional antenna, and forming a beamforming among the coordinated terrestrial base stations (BS)s. We then obtain the optimal beamwidth and suboptimal power allocation so that the TUs' sum-rate is maximized subject to the AU's Quality-of-Service (QoS) requirement. The corresponding optimization problem is non-convex in which we exploit the structure of the problem and apply successive convex approximation (SCA) to obtain a suboptimal solution. We then derive the statistical properties, which consequently enable us to estimate the aggregated ICI. In cases where no interfering BSs have the same elevation angle as the coordinated BSs, we further approximate the AU's outage probability. We then compare the TUs' sum-rate and the outage probability of the ATN-NOMA with multiple existing schemes. Extensive simulation results show that our proposed ATN-NOMA scheme outperforms existing schemes by 52-91% in terms of the sum-rate, and its analytical outage probability can be as low as the order of 10-17. Furthermore, we show that the pairing of AU and TU in multi-cell networks remains beneficial, subject to effective mitigation of ICI.