This paper considers an emerging cellular-connected unmanned aerial vehicle (UAV) architecture for surveillance or monitoring applications. We consider a scenario where a cellular-connected aerial user equipment (AUE) periodically transmits in uplink, with a given data rate requirement, while moving along a given trajectory. For efficient spectrum usage, we enable the concurrent uplink transmission of the AUE and a terrestrial user equipment (TUE) by employing power-domain aerial-terrestrial non-orthogonal multiple access (NOMA), while accounting for the AUE's known trajectory. To characterize the system performance, we develop an analytical framework to compute the rate coverage probability, i.e., the probability that the achievable data rate of both the AUE and TUE exceeds the respective target rates. We use our analytical results to numerically determine the minimum height that the AUE needs to fly, at each transmission point along a given trajectory, in order to satisfy a certain quality of service (QoS) constraint for various AUE target data rates and different built-up environments. Specifically, the results show that the minimum height of the AUE depends on its distance from the BS as the AUE moves along the given trajectory. Our results highlight the importance of modeling AUE trajectory in cellular-connected UAV systems.