What to do when you spot a paper on arXiv with the same essential material as yours?
It seems to me that the best answer is some combination of 1. and 2.  Because you submitted the paper for review before the other work -- call it paper X -- appeared on the arxiv, the community will readily believe that your work does not rely on paper X.  (At first I wrote "completely clear that your work does not rely", but that's too strong: it's possible that you had some prior contact with the authors of paper X and learned about their work before it was published.  But from your description that didn't actually happen, so no problem there.) 

So you are in a fortunate situation: because you submitted the work to the conference before the arxiv posting, you have established your independent priority.  The fact that the report hasn't come back yet has nothing to do with that.  With respect to the submission, it would be reasonable to just wait for the report -- I am assuming that since it is a conference, it will come back within a month or so?  If your paper is accepted, then you should include in the published version and also in your conference talk the information that similar (or the same...) work was independently done in paper X.

However it would be a good idea to write immediately to the authors of paper X and let them know about your work.  If you are in a field where the conference paper will be supplemented by a later journal paper, then depending upon the degree of similarity you may want to consider a joint publication.  If not, then your journal papers should cocite each other: this establishes that "you both have priority", which is certainly possible, and then both works should be publishable.  (But in my opinion a joint paper is the better option if the work is very similar: does the community need two versions of the same work?  Can everyone be counted on to know about and value the two works equally?  Better to join forces: that seals it.)  Depending upon the response you receive and the timing it might be a good idea to post your submission to the arxiv as well, with a note explaining the chronology.

I disagree with both 3. and 4.  First, it does not matter who did the work chronologically first but rather that each work was done independently and before the other was published.  There does not need to be a "winner" and a "loser" here: you can both "win".  It is good that research communities operate in this way, much better than your option 4.: no one has control over which referee report comes back first or which paper goes to press first or anything like that, so if this were the standard it would be at the very least quite unfair and in fact open to all kinds of ethical issues and abuses.

Note: One of the comments asks whether the work was stolen.  It seems that the only plausible way for this to happen is for there to be some collusion between the authors of paper X and either the conference organizers or the chosen referees of your paper.  This type of behavior is in my experience extremely rare, so I don't want to address it in my answer.