So run sshd on a port they don't block. Unless they proxy all traffic you can.

Which is exactly what it is like at the site I am working at currently. The only traffic allowed goes via an HTTP proxy. I need to get around to experimenting with HTTP tunnelling over the proxy.