Single author papers against my advisor's will? I am a third year PhD student in an area of theoretical CS that would like advice for a difficult situation with my advisor.

My advisor is not involved in my research projects at all. In particular, I have come up with all of my paper ideas, and have executed the papers alone. However, she always insists on adding her name as a co-author. This has started to increasingly bother me, as I work very hard on my research and believe I should get credit for that. Note that in theoretical CS, there is no PI is always last author just because of funding tendency, all authors are considered equal and are ordered alphabetically. This makes it particularly bad to just add her, because it is completely ambiguous how much each of us has done.

For my most recent paper, I brought up how I didn't believe she was meeting the IEEE or ACM guidelines for authorship, and told her that I believed I should be sole author on my paper. She agreed that she shouldn't be an author, although she was visibly angry. She said that I was a "weirdo" for doing this, and said that everybody already knows that advisors take credit for their student's work and that publishing with your advisor is the same as publishing alone (this is absolutely untrue). But most importantly, she told me that she would not approve my proposal/dissertation if I did not add her name to several more top-tier papers because then I "have no ties to the university" since I am not working with a professor, and therefore cannot receive my PhD. She also made a lot of other threats, but that was the most relevant to me.

Obviously, I need a new advisor. However, there is really no one in my department in my research area. Switching research areas or departments are not options. So the remaining options are the following:

(1) Add her name to several more papers. I do not like this idea because it is unethical, and there is no guarantee that anything is even gained in this option. She could simply refuse to recommend me in the end after I got her a bunch of papers.

(2) Ignore her threats, and continue working towards my PhD, assuming that she will have to let me graduate. The reasons I don't believe she can stop me from graduating is because (a) I already have a good publication record and my papers are only getting better (b) I have funding independent of her through a fellowship and (c) our dept makes is difficult to kick out graduate students for no real reason. The downside of this is that she won't give me a letter of recommendation, but she doesn't have many connections anyways so this might not be too bad. On the positive side, I will have a bunch of single author papers.

(3) Try to convince a professor in an unrelated research area in my dept to be my advisor, emphasizing that I am independent and can do my work alone. There are a few theory professors in my dept, although they are totally different areas. I have no idea the chance of this working out.

I am also planning on talking to the chair about my situation. But I just wanted to get more of an opinion, what do you think I should do?
You describe behavior that is certainly unethical and should be grounds for dismissal. One doesn't threaten graduate students or try to bribe them (with graduation) for what is in CS, in the US, anyway, improper co-authorship. 

That said, your options are limited. I think the best option is to start with the department chair and see where you stand. If the chair is willing to act ethically you may have a solution, but otherwise you may just need to try to do whatever is necessary to accelerate your graduation and move on. 

One option that the chair might suggest is a mediated meeting with your advisor and either he chair or another faculty member. Your ideas about working independently and getting someone else to sign whatever is needed to graduate might be worth pursuing. 

The problem will then be finding proper letters of recommendation to move you to your next position. That will be difficult unless you cultivate opportunities around you. 

I'm going to also suggest that if the chair isn't supportive that you explore opportunities elsewhere. If other faculty aren't available, it might be worth looking at other institutions. It might actually be less disruptive to do that and someone with a publication record might be seen as a "catch" by another university. 

But I'll guess that your option (2) is the worst. 



Note to readers. Co-authorship by advisors is not the norm in CS and mathematics in many places. My advisor (math) never would have thought of it even though he had substantial contributions to the work, and I never would have considered it for my own students (CS). It would have felt "icky".