Single author papers against my advisor's will?
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".