In this paper, Tomlinson-Harashima Precoding (THP) is considered for multi-user multiple-input single-output (MU-MISO) non-orthogonal multiple access (NOMA) donwlink. Under the hierarchical structure in which multiple clusters each with two users are formed and served in the spatial domain and users in each cluster are served in the power domain, THP is applied to eliminate the inter-cluster interference (ICI) to the strong users and enlarge the dimension of the beam design space for mitigation of ICI to weak users as compared to conventional zero-forcing (ZF) inter-cluster beamforming. With the enlarged beam design space, two beam design algorithms for THP-aided MISO-NOMA are proposed. The first is a greedy sequential beam design with user scheduling, and the second is the joint beam redesign and power allocation. The two design problems lead to non-convex optimization problems. An efficient algorithm is proposed to solve the non-convex optimization problems based on successive convex approximation (SCA). Numerical results show that the proposed user scheduling and two beam design methods based on THP yield noticeable gain over existing methods.