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**

1. R. Bhatia. *Positive definite matrices*  (Chapter 5)
2. R. B. Bapat and T. E. S. Raghavan. Nonnegative matrices and applications (Chapter 4)
3. Kh. D. Ikramov and N. V. Savel'eva. *Conditionally positive definite matrices*, J. Mathematical Sciences, Vo. 98, No. 1, 2000.
4. 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)