Block facebook even in the case users get their hands on tor, freegate and similar applications

I've been using, happily, opendns to block facebook on my network. Then I started thinking about tricks to circumvent this block and, of course, I've read here on serverfault how to block the facebook ip address. But if someone uses tor or freegate?

What can I do?

What you have isn't really a technical problem, it's a management problem, don't try to make it a technical problem. You need to have an acceptable use policy that clearly defines what users can and can't do with the resources provided by your organisation. This should also detail what steps may be taken to enforce the AUP (monitoring usage/auditing machines etc) and what the sanctions for breaking the AUP are.

I think you need to ask Why you are trying to block Facebook? I'm assuming this is a corporate network not home. Why should you allow your staff to use myspace, twitter and amazon, friends-reunited etc but not Facebook? This sort of corporate content filtering (the organisation I work for does this as well) is almost always pointless. It tries to block websites it considers rude. Why? I'm a grown-up (most of the time), I can deal with rude words. My org tries to block webmail to prevent us e-mailing information home, but it doesn't block my ntl webmail becuase the person setting up the rules didn't think of it. Nor does it block my personal webmail server.
I'm all in favour of companies monitoring the web usage of staff, and having management policies in place to say what is considered acceptable web usage, both work related and personal. But the automated blocking of sites is annoying (especially in the case of a false positive) and is ultimatly not actually going to prevent anything significant. Save yourself the hassle, make sure the proxy virus scans content and downloads and that your firewall is configured well, leave the policing your users internet habits to their managers.

The harder you try to block it, the harder the users will try to get access to it.

What can I do?

The old-fashioned means for enforcing similar "productivity policies" remains: get managers watching over employees' shoulders whenever a TPS report is late (or the wrong cover sheet is used).

Well, for starters (beyond what everyone else said about policy and governance), you should be blocking egress traffic on your network outside of what's required (and I generally don't allow client machines to make direct TCP/UDP connections anywhere; there's no need 99% of the time when you have a proxy server in-house), especially UDP/TCP 53 to outside DNS servers.

I've used Layer 3 filtering and OpenDNS together with alot of success at clients (such as yours) that are not treating this like a management problem (which it is). However, if they want to pay me to come in and set this up after explaining that then so be it.

Even better than dropping outbound DNS would be to setup a proxy server (Squid is open source/free and does a good job caching as well; depending on your size, aging workstation hardware is likely fine).

Now you can drop all direct TCP/UDP connections from the clients to the outside and force everyone to use a proxy (transparently, and they won't even notice).