Does hook_node_access_records() and hook_node_grants() change permissions for existing nodes? When I install a new module containing hook_node_access_records() and hook_node_grants(), Does it change permissions for existing nodes? Or it affects only on new nodes?

If it doesn't change permissions for existing nodes, Is there a way to rebuild node_access table?
You can implement hook_enable() and call node_access_needs_rebuild(TRUE), see user_relationship_node_access_enable() for an example.

That doesn't actually do much on its own, but Drupal will then automatically print a message to administrators and inform them that the permissions need to be rebuild and also includes a link to the place where this can be done.