You've done a good job of enumerating the options, and you're definitely on the right track. As you've discovered, there's no way to query based on security rules. This was done intentionally, since (depending on your security rules) this could be quite expensive (Firebase avoids complex queries in general for this reason).
So your method 3 is the exact right way to do this. Duplicating data for these sorts of situations is actually a very common practice. See Denormalizing Your Data is Normal for a blog post that goes into more detail on this.
You could also do method 1 with the duplicated document list. This is especially useful if you want to be able to "invite" somebody to a document just with a URL (that contains the secret ID). Or you could do a combination of the two (have some documents be "public but unlisted" and some be "private to invited friends" or whatever.)