Unmanned aerial vehicles (UAVs) are expected to be an important new class of users in the fifth generation (5G) and beyond 5G cellular networks. In particular, there are emerging UAV applications such as aerial photograph and data relaying that require high-speed communications between the UAVs and the ground base stations (GBSs). Due to the high UAV altitude, the strong line-of-sight (LoS) links generally dominate the channels between the UAVs and GBSs, which brings both opportunities and challenges in the design of future wireless networks supporting both terrestrial and aerial users. Although each UAV can associate with more GBSs for communication as compared to terrestrial users thanks to the LoS-dominant channels, it also causes/suffers more severe interference to/from the terrestrial communications in the uplink/downlink. This paper studies the uplink communication from a multi-antenna UAV to a set of GBSs within its signal coverage by considering a practical yet challenging scenario when the number of antennas at the UAV is smaller than that of co-channel GBSs. To achieve high-rate transmission yet avoid interfering with any of the existing terrestrial communications at the co-channel GBSs, we propose a novel multi-beam transmission strategy by exploiting the nonorthogonal multiple access (NOMA) technique. Specifically, the UAV sends each data stream to a selected subset of the GBSs, which can decode the UAV's signals and then cancel them before decoding the messages of their served terrestrial users, and in the meanwhile nulls its interference at the other GBSs via zero-forcing (ZF) beamforming. To draw essential insight, we first characterize in closed-form the degrees-of-freedom (DoF) achievable for the UAV's sum-rate maximization under the proposed strategy. Then, we propose an efficient algorithm to jointly optimize the number of UAV data streams, the data stream-GBS association, and the transmit beamforming to maximize the UAV's transmit rate subject to the interference avoidance constraints for protecting the terrestrial users. Numerical examples are provided to verify the effectiveness of the proposed NOMA-based multi-beam transmission strategy.