Is there an optimal method to grant permissions for a newly added permission defined by hook_permission?
The only reason Drupal would not know of the new permission is because it hasn't yet registered your hook. This would only happens after a cache clear.

I would not advise to run a full cache clear before an update (as that might well invoke code that will expect the update to have been run already). Maybe you could get away with clearing the cache of hooks in module_implements. You could call this in your hook_update_N before setting the role:

module_implements('permission', FALSE, TRUE);


But even that feels a bit risky ; it is best not to interfere with the way things run, you might end up with debugging headaches.

Otherwise I don't think there is a perfect solution. Drupal just doesn't have a 'post-update' style hook. You could implement such a hook yourself (maybe using a variable_get/set and hook_init ; or as a drush script as you suggest), however this feels like a complicated way to do what could otherwise be done with a simple SQL query.

If you know your target uses an SQL database, then I think that, while not entirely satisfying, the SQL insert statement is the simplest solution.