I'm trying to figure out how to search for contacts (individuals) that do not have a "Current Employeer" relation.
Is that possible?
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!