Is there a way to enforce uniqueness on a custom field in a custom record without scripting? In other words, I don't want users to save the custom record if the value in the name field already exists.

No

If I have a saved search condition for the return user error action, wouldn't that work?

The problem with a Saved Search is that the record needs to be saved for the search to "run" on it. So it would be saved as a new record then your could use a search to find duplicates and then display some sort of warning message. But couldn't do a Before Submit or anything because the record doesn't necessarily "exist" Before Submit