I don't think there is any point in writing to the EiC, if you don't want to actually appeal the decision. I would simply send a note to the AE who handled the paper:

Thank you for handling my paper. I accept your decision. I would simply like to state that the results in my paper were obtained independently, and I had no previous knowledge of the unpublished manuscript mentioned by Reviewer #4. I will look forward to reading and citing this paper when it becomes publicly available.

Then submit your paper somewhere else, quickly (though after making any revisions suggested by these reviewers). I would be inclined to include a comment to the new journal's editor, saying that you have heard there is a paper under review somewhere with similar results, but you have been unable to obtain a copy of the paper or any further information about it. You could also emphasize that you have obtained your results independently of any other reseacher / group.

There are many cases of simultaneous discoveries in history, so don’t let others take your credit when it’s not justified. This story could also be inspiring.

1. If your field has a preprint culture and your target journals allow for this, publish a pre-print of your paper immediately. This way you can establish with a certain confidence that you arrived at your results independently – assuming that there is no pre-print of the alleged other paper (and even then, the difference in time may be sufficiently short to be regarded as evidence for independent discovery).

   If you cannot publish a pre-print, at least obtain a time stamp of your paper. While it may not help you in the and, at least some ways (in particular publishing a hash of your paper) are almost no effort.

2. I would argue that the only acceptable evidence of the other paper is the paper itself. Now how could the journal have obtained this?

   • The other paper is publicly available (e.g., on a pre-print repository) or its authors have allowed for a free dissemination of the pre-print. In this case, you should be given the information needed to access the paper.

   • The reviewer had the paper under some restrictions and shared it with the journal. This very likely means that the reviewer violated these restrictions (peer-review confidentiality or trust by the authors). I can contrive some exceptions like the authors sharing the paper with the reviewer and allow them to share it if they happen to peer-review a similar paper – but that’s, well, contrived.

   • The other paper’s authors explicitly gave it to the journal that rejected your paper (or agreed that it is given to them). This poses the question: How did the authors of the other paper know about this, or how did the journal know whom to ask? Keeping in mind that the reviewer cannot ask the authors back without breaching peer-review confidentiality, this leads us to slightly modified variants of the previous points: If the reviewer can freely share the identity of the other paper’s author, they can also share it with you. If the reviewer cannot freely share the identity, they almost likely breached some kind of trust.

   • The reviewer was able to share it due to being an author of the paper. This is a clear conflict of interest.

   • The journal doesn’t have the paper and just relies on the reviewer’s word.

   Either way, this would be very fishy and I see good reasons for appealing to the journal’s decision (or making a scandal out of it).

3. The existence of another paper going in a similar direction does not mean that you plagiarised it, but it does evidence that the topic is indeed relevant. Moreover, if the other paper has not been accepted yet, it may very well that the peer review found flaws that your paper doesn’t have. All of this are good arguments for any journal (either the one that rejected your paper or another one) to accept your paper, if the quality of the research is undisputed.

I disagree with some of the interpretations you're being offered.

Given that you've reached a stage of peer review, you are entitled to a rigorous review supported by the current state-of-the-art of your field that is accessible to any expert of the field. This does not include super-secret documents that nobody has privilege to disclose. If the referee in question cannot point you to an accessible abstract or preprint, the document in question should not be part of the referee's review. Simply put, the referee, if he or she cannot ignore the privileged information for the purposes of review, is in conflict, and submitting the review as you received it was not wise (the story is slightly different if the manuscript referred to is floating around the offices as a submission to the journal you submitted to, as the section editor holds the information).

Further, if the secret manuscript in question is from the group or recent coauthor of the referee (assuming it even exists), that referee probably has committed a fairly serious ethical breach by not exposing the conflict when it became apparent.

What to do? There probably isn't a great answer. If the main reason for rejection was the submitted document referred to, my suggestion would be to respond to the reviewing editor with the opinion that you feel you're entitled to a review informed by the available state-of-the-art; the review you received wasn't. Thus, you feel that this referee is in conflict (indeed, this would be a sound and punctate basis for an appeal). Request an additional review, with the review in question tossed. You should consider asking if the secret manuscript in question comes from the referee's group -- in which case the editor should strongly consider not using that referee in the future.

Whether you cc the EiC is up to you. It's a tough call.

Alternatively, simply resubmit to another journal. I would be less inclined to do this, as I think a fair review process is worth defending. If you decide to appeal, I recommend making a point of asking the editor for a timely decision as to whether you will receive a re-review.

A few additional points -- nobody is accusing you of plagiarism. Also, published manuscripts typically contain the dates of the original submission, so provenance of the ideas is not really at issue.