If $A$ is symmetric, then the matrices that you mention are called:
Conditionally positive definite (CPD) --- these are intimately related to the venerable infinitely divisible matrices
There is a vast amount of literature on these matrices, some useful pointers can already be found in R. Bhatia's wonderful book: Positive definite matrices
There are some basic algorithmic approaches to check whether a matrix is CPD or not (e.g., Ref. 3 below)
A simple characterization is given by the following. Let $A$ be an $n \times n$ Hermitian matrix, and let $B$ be the $(n-1) \times (n-1)$ matrix with entries
$$b_{ij} = a_{ij} + a_{i+1,j+1} - a_{i,j+1} - a_{i+1,j}$$
Then $A$ is CPD if and only if $B$ is positive-definite.
References
- R. Bhatia. Positive definite matrices (esp. Chapter 5)
- R. B. Bapat and T. E. S. Raghavan. Nonnegative matrices and applications (Chapter 4)
- Kh. D. Ikramov and N. V. SaveFeva. Conditionally positive definite matrices, J. Mathematical Sciences, Vo. 98, No. 1, 2000.
- R. A. Horn. The theory of infinitely divisible matrices and kernels (e.g. here : http://www.ams.org/journals/tran/1969-136-00/S0002-9947-1969-0264736-5)/S0002-9947-1969-0264736-5.pdf