This turns out to be more complicated that I first thought it'd be. Apparently the graphs you are asking about are usually called *normal digraphs* and a proper characterization does not seem to be known. [This recent paper][1] treats characterization in the special case of Cayley digraphs and also refers to previous work on other cases (alas, almost all of it is in not-immediately-accessible-online places).

There is case, I think, that is easy to work out: graph where in-degrees equals\ the out-degrees. The [write-up here][2] indicates (once again, based on a 2005 paper I can't access here and now) that such graphs (called *balanced*) have a normal Laplacian matrix, which is easily seen to be equivalent to having a normal adjacency matrix.


  [1]: http://www.sciencedirect.com/science/article/pii/S0012365X0900017X
  [2]: https://sites.google.com/site/identicalsynchronization/properties-of-directed-graph-laplacian-matrices