As pointed out by Michael Banck as a comment on my blogpost, the pg_rewind documentation says it requires superuser permissions on the remote server.
Is that really so, though? I haven't tested it, but from a quick look at the code it looks like it needs pg_ls_dir(), pg_stat_file() and pg_read_binary_file(), all, of which are independently grantable.