I can't really return the status in $! since it isn't an errno value.

No, but nothing is stopping you from making your own global (package) variable or object attribute. For example, DBI has $DBI::err and $DBI::errstr.

You could throw an exception object, where one method returns an error code and another returns an error string.

You could return an error object that overrides booleanification (false on error), numification (error code) and stringification (error message), but that's probably too magical.