Did you try the texture space painting mode (first painting button to toggle). It definitely has to be improved on seams, but should be pretty close to "surface normals based".
I don't think I have! I'll try it out when I can!
