Here are two possible workarounds.
Enlarge the vertex size and place the labels within the vertex. Of course, this also depends on the length of the labels, but for shortish labels it works well, whereas your example above clips off any label of more than one character for vertex 1.
ex:
Table[Graph[{1 -> 2, 2 -> 3, 3 -> 1}, VertexSize -> 0.3,
VertexLabels -> Table[i ->
Placed["vertex" <> ToString[i], p], {i, 3}],
VertexShapeFunction -> "Square", PlotLabel -> p],
{p, {Left, Top, Right, Bottom, Center}}]
Use tooltips to store the labels instead of displaying them on the graphic. [Edit: Center probably looks the best, and then you can wrap labels by putting \n in your string if you need to, but again, depends on the label length.]
ex:
Graph[{1 -> 2, 2 -> 3, 3 -> 1}, VertexLabels -> Placed["Name", Tooltip]]
While this stops you from being able to see all the labels at the same time, you never have any clipping.