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. Once I find the paper in my archives, I will update my answer.

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.