Scarcity of the radio spectrum and high inter-cell interference (ICI) are major impediments to efficient connectivity in cellular-connected unmanned aerial vehicles (UAV)s. To address these issues, we propose aerial-terrestrial network non-orthogonal multiple access (ATN-NOMA). In the 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 communication. The high ICI issue at the AU receiver is further managed by equipping the AU with an adjustable beamwidth directional antenna and forming a distributed beamforming among the coordinated terrestrial base stations (BSs). The proposed ATN-NOMA scheme obtains the optimal beamwidth and power allocation to maximize the TUs' sum-rate subject to the AU's Quality-of-Service (QoS) requirement. The corresponding optimization is a non-convex optimization problem for which we exploit the structure of the problem to obtain a local optimal solution. We further compare TUs' sum-rate and AU's outage probability of the proposed scheme with multiple schemes. Simulation results show that our proposed scheme significantly outperforms the existing schemes and further demonstrate a robust performance against UAV altitude variations.