Higher-order and black-box clustering
One example of what you might call non-linear clustering is kernel-based clustering, where the similarity function is described by a (non-linear) kernel function. This is a weak form of non-linearity, since there's a lifting map that makes everything linear (albeit in a Hilbert space)