What's a fast algorithm to decide whether there is an $A_G$ corresponding to a given $\chi_G(\lambda)$?
The short answer is no. No quick algorithm for this problem is known. 

A big open problem (for at least 50 years) in algebraic graph theory asks about  the existence a regular graph of degree 57 order 3250 girth 5 and diameter 2. This is known as a Moore graph.

However, it is known that if such a graph exists its characteristic polynomial has to be $p(x) = (x-57)(x+8)^{1520}(x-7)^{1729}$ [1, Proposition 1].

So if there would be a quick solution to your problem, this big open problem would  be solved already.

In fact, the theorem that you stated can be further generalized. The $i$'th coefficient of the characteristic polynomial of $G$ is given by $$(-1)^{i}c_i = \sum (-1)^{r(H)} 2^{s(H)}$$ where the summation is taken over all subgraphs $H$ of $G$ that have order $i$ and whose connected components are $K_2$ and cycles. The function $s(H)$ counts the number of components of $H$ that are cycles while $r(H)$ denotes the rank of $H.$



[1] M. Macaj, J. Siran. Search for properties of the missing Moore graph, Linear Algebra Appl., 432 (2010), 2381–2398.