A new combinatorial property for the character table of a finite group?

By standard manipulations with the group algebra, your sum has a combinatorial/probabilistic interpretation that makes its nonnegativity clear.

The element $ \frac{1}{|G|} \sum_{ g\in G} [g hg^{-1} ]$ in the group algebra is conjugacy invariant, and so acts by scalars on each irreducible representation. Because its trace on a representation with the character $\chi$ is $ \frac{1}{|G|} \sum_{ g\in G} \chi( g hg^{-1} ) = \frac{1}{|G|} \sum_{ g\in G} \chi( h )= \chi(h)$, its unique eigenvalue must be $\frac{\chi(h)}{\chi(1)}$. Hence for $h_1,h_2,h_3$ three elements of the group,

$$ \left( \frac{1}{|G|} \sum_{ g\in G} [g h_1g^{-1} ]\right) \left( \frac{1}{|G|} \sum_{ g\in G} [g h_2g^{-1} ]\right) \left( \frac{1}{|G|} \sum_{ g\in G} [g h_3g^{-1} ]\right) $$

acts on this representation with eigenvalue $\frac{ \chi(h_1) \chi(h_2) \chi(h_3)}{\chi(1)^3}$.

Now the group algebra, as a module over itself, is the sum over irreducible characters $\chi$ of $\chi(1) $ copies of the representation with character $\chi$. Hence the trace of this element on the group algebra is $$\sum_{\chi} \chi(1) \cdot \chi(1) \cdot \frac{ \chi(h_1) \chi(h_2) \chi(h_3)}{\chi(1)^3}= \sum_{\chi} \frac{ \chi(h_1) \chi(h_2) \chi(h_3)}{\chi(1)}.$$

On the other hand, the trace of an element of the group algebra on itself is the order of the group times the coefficient of $[1]$. The coefficient of $[1]$ in this particular element is $\frac{1}{ |G|^3}$ times the number of $g_1,g_2,g_3$ such that $g_1 h_1 g_1^{-1} g_2 h_2 g_2^{-1} g_3 h_3 g_3^{-1} =1$. This gives the combinatorial interpretation

$$\sum_{\chi} \frac{ \chi(h_1) \chi(h_2) \chi(h_3)}{\chi(1)} = \frac{1}{ |G|^2} \left| \{ g_1,g_2,g_3 \in G \mid g_1 h_1 g_1^{-1} g_2 h_2 g_2^{-1} g_3 h_3 g_3^{-1} =1 \}\right|$$

from which non-negativity is clear.

I would guess this is probably in the group theory literature somewhere but I wouldn't know where.

This is indeed well-known in the character theory literature, and goes back to Frobenius and Burnside. What you are calculating is a positive rational multiple of a class algebra constant, and class algebra constants are clearly non-negative.

Using the notation in David Speyer's comment, it is well-known, and derived in most representation theory texts that $\frac{|G|}{|C_{G}(f)| |C_{G}(g)|} \sum_{\chi} \frac{\chi(f)\chi(g)\chi(h)}{\chi(1)}$ is the number of times $h^{-1}$ is expressible as a product of a conjugate of $f$ and a conjugate of $g$. The character theory formula is easily derived from the expressions of the class sums as linear combinations of primitive central idempotents of the group algebra $\mathbb{C}G$, and can be found in many texts .