If you are interested in using Mercurial on your own project and are simply worried about hosting, here's a list of providers: https://mercurial.selenic.com/wiki/MercurialHosting
If you are thinking of using Mercurial when the rest of your team uses Git, then I would just suck it up and learn Git (or convince your team to switch). It is not, by any means, the most complicated thing you have to learn for your job ;-).
Back in the bad old days when I was forced to use Visual Source Safe for version control, we used to maintain our code in multiple repositories -- using CVS for development and simply pushing to VSS when features were complete. That kind of tactic is still open to you, but the overhead is rather large for the minimal difference between Git and Mercurial.
Sounds interesting. So was this basically a team of 'bandits' secretly using a non-endorsed VCS to collaborate and get shit done, and then pushing to VSS to keep the pointy-haired boss happy?
As you might imagine (the use of GPL software banned, the use of MS software enforced), the rules were politically rather than technically oriented. There were rumours that we had an agreement with MS to follow these rules and I wouldn't say it was out of the question. By and large as long as you followed the letter of rules nobody cared much after that. Using CVS was rather a major coup, though, given the GPL licence.
Possibly younger people will be amazed at the ridiculous conditions some people worked under back then. After I left that position I swore I would never agree to work with restrictions like that. In fact, the ability to work on free software is one of the first things I bring up as important to me in a job interview. Even a slight hesitation is enough to make me walk.
Honestly, I also think github's defacto status is a major obstacle to adoption.
There are actually projects that let you work with an hg/git repo and push to the other type. http://hg-git.github.io/ for instance. No idea if these things are production ready or not though.