If this was headlabel or taillabel, you could try setting labeldistance to zero to force the label to be drawn on the edge, but as I understand, you are referring to edge label (the one on the middle of the edge). Documentation quite clearly states that labeldistance only affects headlabel and taillabel labels, but you can try your luck.
One other thing you might want to try is to make a transparent, intermediary node with a label on it. It could look like you want… But if you heavily rely on node placement algorithm, it could be unacceptable to create those ‘artificial’ nodes. In that case, I encourage you to join graphviz developers and add the feature you need 😉 Seriously, it is very satisfying.
If you find another solution, please post it. I will be facing a similar problem in the near future.