After few days of mobile tethering, I realized I could ask their HTTP proxy to open an HTTPS connection to a server outside the network, but instead of sending HTTPS traffic through the proxy, I could send any traffic - like SSH. With this, I was ultimately able to open an SSH-tunnel to my own shell server running OpenVPN outside their network, which then allowed a (surprisingly stable and fast) access to the internet at wide – via an OpenVPN-tunnel wrapped in an SSH-tunnel pretending to be an HTTPS-tunnel.
I don't recall whether ICMP was allowed out at the BigCorp., but I am pretty sure someone will one day find a tool like this quite useful in a similar situation.. :)