Grant/refuse access permission on the fly
Yes. Look into this topic: Node access rights.

That's what you should do if you want the permissions to be respected in all contexts, including DB queries (except your own if you don't use db_rewrite_sql).

Another potential solution, assuming that you can get your existing setup to work with it, is Content Access. It can do per-user access control. The way I would do this is implementing hook_nodeapi's update operation and then programmatically configuring Content Access to match the list of users. Basically, the list of users would become a simplified admin interface in this approach. You would of course have to look at how Content Access manages this specifically (I know it uses the ACL module).

This approach should have all the benefits of the previous one, i.e. low-level security.

The poor man's way to do this would be to use hook_menu_alter and change access callback/access arguments to your own, where you'd load the nodes and do your fancy checks. This would only help on viewing, though, not on data retrieval. But it is probably easier than the other two ways if you don't need a perfect solution.