How can I include a .inc file before hook_node_access runs?
First, using the require include to load your file is perfectly sound, I think. Alternatively, you could add the include to the .info file of your module and allow it to be loaded on every page.

However, to answer your question: We could implement hook_hook_info() from a custom module and add node_access as a group for hook_node_access(). Now, in our module itself, we can have our access callback in a mymod.node_access.inc file.

This is probably not recommended as we are dabbling with core (in a small yet unreliable way) with no real value at all but is a way by which you could do it.

Once you have done this, I'd suggest running the entire Drupal core test suite once (at least node module's) to make sure that we are okay.