Additional ways to transform to `Graphics` and post-process the `Graph` output: 

    Show[Graph[{Labeled[a->b,"A"],Labeled[a->b,"B"]}]]/. 
       Text["A",{x_,y_/; (y<0.)},z___]:>Text["B",{x,y},z]

![enter image description here][1]

Or

    Show[Graph[{Labeled[a->b,"A"],Labeled[b->a,"B"]}]]/. 
      BezierCurve[{{-1.,0.},m_,y_}]:>BezierCurve[{{1.,0.},m,{-1.,0.}}]
    (* same picture *)

**Update:** Using `EdgeShapeFunction`:

    labels=Reverse@{"A","B","C","D"};
    i=1;
    Graph[{a->b,a->b,a->b, a->b},
     EdgeShapeFunction->({Text[labels[[i++]],Mean@#],Arrow@#}&)]
![enter image description here][2]


  [1]: https://i.sstatic.net/K9nTv.png
  [2]: https://i.sstatic.net/ddntg.png