Calculating ultrametric distance matrix
In my understanding you cannot skip the tree construction, since there is no guarantee that the pairwise distances are compatible with a tree, even for non-ultrametric trees. That is, to create a pairwise distance matrix that reflects patristic distances between tree leaves you need to create a tree first. Even without the ultrametricity condition. 

The complicating factor here is that distance matrices compatible with trees must also respect distances to unobserved internal nodes...
This blog post about how to make a tree ultrametric might be relevant.