Definition - center of the cluster with non-Euclidean distance
The easiest solution for a non-Euclidean cluster center is the medoid, as in the algorithm PAM. This works with arbitrary metrics, but unfortunately for a 2-element cluster the result by definition is random (by metric properties, each point is an equally good medoid).

Or you step back and rethink what the center is. It is the point which has the least squared error. So "all" you need to do is solve some math for your distance function, how to optimize this least-squares estimation. People have been solving such problems since Gauss. For example with the deviation abs(x-mu) the least-squares objective is minimized by the arithmetic mean, an the one dimensional result carries over to the n-dimensional case and thus Euclidean distance!

Obviously, this needs to be done for every distance function again.

So if you want to interpolate a center for an other distance function, solve that optimization problem (efficiently, but try to find an existing solution first, of course).