There is a short proof based on coupling. Let $Y$ be a r.v. with the same distribution as $X$ and independent of $X$. Then $f(X)-f(Y)$ and $g(X)-g(Y)$ are centered r.v.'s.
On the one hand,
$Cov(f(X)-f(Y), g(X)-g(Y))= \mathsf{E} (f(X)-f(Y)) (g(X)-g(Y))\ge 0$. (actually $>0$ unless $g(X)$ or $f(X)$ is constant a.s.)
On the other hand,
$Cov(f(X)-f(Y), g(X)-g(Y))=$
$= Cov(f(X),g(X))-Cov(f(X),g(Y))-Cov(f(Y),g(X))+Cov(f(Y),g(Y))=2Cov(f(X),g(X))$
Combining these two lines we get $2Cov(f(X),g(X))>0$.
A couple of relevant remarks:
1.This statement is also due to Chebyshev.
2. The property can be formulated as "One r.v. forms an associated family". In general, r.v.'s $X_1,\ldots, X_n$ are called associated if for any two bounded coordinatewise nondecreasing functions $f$ and $g$, $Cov(f(X_1,\ldots,X_n),g(X_1,\ldots,X_n))\ge 0$. There is a recent book by Bulinskiy and Shashkin on association.