If the surfaces are exactly co-planer, your fate is up to the FPU gods; you'll more than likely have Z-fighting. If the triangles are identical and you do the exact same math to each, you will end up with the same Z-values for both. But again, this will only happen if your math operations are identical for both. (Since, in general, FPU operations are not commutative)
One possible solution is to not use the Z-buffer at all. Rather you can use the Painter's Algorithm. Granted, this comes with all the problems of the painters algorithm as well. But, it would solve the Z-fighting.
In your example case of Screen Space Decals (SSDs), the common solution is to use an offset, aka a simple thin cube. See Warhammer 40k's presentation about SSDs for reference. Or Bart Wronski's post which addresses some other issues with decals, but also links to a few other presentations about SSDs