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.