We study the spin-spin coupling between two single-electron quantum dots due to the Coulomb and spin-orbit interactions, in the absence of tunneling between the dots. We find an anisotropic XY spin-spin interaction that is proportional to the Zeeman splitting produced by the external magnetic field. This interaction is studied both in the limit of weak and strong Coulomb repulsion with respect to the level spacing of the dot. The interaction is found to be a nonmonotonic function of interdot distance a(0) and external magnetic field and, moreover, vanishes for some special values of a(0) and/or magnetic field orientation. This mechanism thus provides a new way to generate and tune spin interaction between quantum dots. We propose a scheme to measure this spin-spin interaction based on the spin-relaxation-measurement technique.