Is this stronger statement of the squeeze theorem valid?

Your weakened hypothesis is equivalent to $\min(g(x), h(x)) \leq f(x) \leq \max(g(x), h(x))$. So, define $m(x) = \min(g(x), h(x))$ and $M(x) = \max(g(x), h(x))$ and the hypothesis $m(x) \leq f(x) \leq M(x)$ applies. So, is your version really more general?

There is really not more information to be gained. In the situation you describe, you can define new functions $g_1=\min\{g,h\}$, $h_1=\max\{g,h\}$ and use the regular squeeze theorem with $g_1\leq f\leq h_1$.

On a more practical point of view, in the vast majority of uses of the squeeze theorem the $g$ and $h$ are monotone.

Your reasoning is right.

If, for all $x,$ either $g(x)\le f(x)\le h(x)$ or $h(x)\le f(x)\le g(x),$ then $$\min\{g(x),h(x)\}\le f(x)\le\max\{g(x),h(x)\}$$ for all $x.$ So all we have to do is show that, if $g(x)\to L$ and $h(x)\to L,$ then $\max\{g(x),h(x)\}\to L.$ (Of course it follows that $\min\{g(x),h(x)\}=-\max\{-g(x),-h(x)\}\to L$ as well.)

Observe that $$\max\{g(x),h(x)\}=\frac{g(x)+h(x)+|g(x)-h(x)|}2\to\frac{L+L+|L-L|}2=L.$$