Ball Tree and Pseudometrics
I think a pseudometric should be fine.

The BallTree's ability to limit the number of distances to compute relies heavily on the triangle inequality, and (perhaps to a lesser extent) symmetry.  And nonnegativity certainly seems critical.  At the very least, the code in sklearn will probably in places tacitly assume symmetry and nonnegativity.

In a pseudometric, the relation "distance 0" is an equivalence relation, and the distance naturally extends to the quotient space, where it is an honest metric.  So I think for BallTrees, it really shouldn't matter; any ball that contains a given point will also automatically contain all its "equivalent" points.