In truth though if you start considering your employees like the enemy it's just a never ending upwards battle, especially if your employees are comp-sci folks. You could tunnel SSH over HTTP or even DNS if you cared enough.
Then in firefox (or other), the socks proxy is on localhost port 4242.
Similarly, good security people know that port filtering is a losing game unless you are willing to restrict everything to a known-safe whitelist – the malware authors do work full-time on tunneling techniques, after all – and may be focusing their efforts on endpoint protection or better isolation between users/groups.
In any case you are left with no SSH, or somebody watching your ssh and have control over your ability to tunnel.
The best you can do with these boxes is make a sub tunnel over one of the protocols that they do allow through, you just can't rely on the primary encryption provided by the protocol that the middle box is executing MITM on. If somebody actually looks at the traffic they will see that you are not transferring plain text at the middle box, so that might raise some eyebrows.
For instance if your policies are too restrictive people will use their smartphones more and more to access the internet. Then some will start doing work stuff on their smartphones and you lose all control. What do you do then? Forbid smartphones within the company? Fire everybody you catch using one? It's just an arms race at this point.
Sane security measures and some pedagogy go a long way. Easier said than done though, it's a tough compromise to make.
While unfortunately for TLS client certificates are not a solution against MITM due to their awful user experience and privacy concerns, for SSH public key authentication has a good user experience, and is very common.
