Improving on the line of thought in that other answer, we can craft something that exactly matches the requirement. We'll use $7$ arbitrary distinct $256$-bit strings $k_0\dots k_6$, and a $256$-bit PRF $P(k,m)$ such as $\mathtt{HMAC}_\mathtt{SHA256}(k,m)$.
For $j\in\{1,2\}$, define $\hat H_j(s,x)$ as the $512$-bit string $ (K_j||P(k_j,s))\oplus x$, where $||$ stands for concatenation, $\oplus$ stands for bitwise-XOR, and $x$ is restricted to $512$-bit strings. We have the desired property $\hat H_1(s_1,\hat H_2(s_2,x))=\hat H_2(s_2,\hat H_1(s_1,x))$. However these $\hat H_1$, $\hat H_2$ make rather poor hash functions. In particular, the output is malleable using the second input.
In order to improve on that, for $j\in\{1,2\}$, define $\tilde H_j(s,x)$ as the $512$-bit string $\hat H_j(s,x)$ when $x$ is a $512$-bit string which left $256$ bits match $k_j$, and $\hat H_j(s,(k1\oplus k2)||P(k_0,x))$ in all other cases. We have the desired property $\tilde H_1(s_1,\tilde H_2(s_2,x))=\tilde H_2(s_2,\tilde H_1(s_1,x))$, and these functions are only malleable for a small range of their second input, highly characteristic of the output of the other function.
We just need some added camouflage. Define a $512$-bit permutation $E()$ as the 4-round Feistel cipher with round functions $P(K_3,r)\dots P(K_6,r)$, and $D()$ the reverse permutation. These are known secure. Define $H_j(s,x)$ as $E(\tilde H_j(s,D(x))$ when $x$ is a 512-bit string, and $E(\tilde H_j(s,x))$ otherwise. The desired property $H_1(s_1,H_2(s_2,x))=H_2(s_2,H_1(s_1,x))$ is met, and knowledge of at least some of the $K_i$ constants seems necessary to distinguish $H_1$ and $H_2$ from a random oracle, except for consequences of that property.