How to search for contacts without a specific relation?
The search builder should be able to give you this as it has a larger range of search operators available to you. 

Head to Search > Search builder and then use the criteria:

Contacts > Current Employer ID > Is Null

That should return everyone who has no value for your current employer field. 

Hope that helps!