We study gradient models for spins taking values in the integers (or an integer lattice), which interact via a general potential depending only on the differences of the spin values at neighboring sites, located on a regular tree with d + 1 neighbors. We first provide general conditions in terms of the relevant p-norms of the associated transfer operator Q which ensure the existence of a countable family of proper Gibbs measures. Next we prove existence of delocalized gradient Gibbs measures, under natural conditions on Q. This implies coexistence of both types of measures for large classes of models including the SOS-model, and heavy-tailed models arising for instance for potentials of logarithmic growth.