First, as noted by others, I too find it hard to believe you could get a work permit in any country without a signed contract with the employer. However, it's not clear if the contingency blocks you from obtaining the contract, or if it is merely a clause in a the contract. If it's just a clause, your worry may be a bit misplaced: if you don't secure your permit, it doesn't matter one whit what the contract says, you won't be able to take the job. It's not crazy for the employer to spell that out.
Second, and more importantly, what is the employer doing to support your application for the permit? I emmigrated to Germany and it's absolutely common advice and practice that the employer start the application process for the work permit, here, as they can get it done in a few weeks, as opposed to several months if the employee has to do it themselves. As far as I know it cost my employer nothing but a bit of HR's time. So what is your prospective employer doing/willing to do, to help secure your permit?
In most cases, the employer should feel some motivation to secure your permit as quickly as possible. If they are not assisting you I think this tells you A LOT about the quality of this employer and you may want to seriously rethink this.
However we still have no hint what country you might be moving to...really, it's important to know that.