Is it possible to recover after completely botching my best chances to get a PhD?
(1) If you're in computer science, then even failing to get into a PhD program immediately after finishing your master's degree is not an insurmountable road block. There are even industry projects you can work on to improve your application.
(2) Yes, it is ultimately a roll of the dice. Some advisors are, in fact, just assholes who will ruin your career, and there's no amount of due diligence that will completely remove the chance of finding one. It's horribly unfair that a choice that will determine your career and entire life will depend on making a random die roll, but there's really nothing you can do about it; you have little power as a prospective grad student. (And don't expect much understanding or sympathy here; this board is mostly composed of people who have made that roll, and don't realize the amount of luck involved or that there was a die roll in the first place. The same remark applies to a wide variety of such die rolls in life.)
(3) Few people will say so explicitly, but yes. You have little power in the advsior/student relationship; and as a student (and not even one of his PhD students), you're probably beneath his notice. It is also massively unfair, but see point (2).
It looks that your relations with this professor are coming to an end, and you can't rely on his future support. That's a shame; however, there's still a plenty of fish in a water, and hopefully enough time to get some.
Why don't you focus on establishing some contacts with another professor or lecturer in your university? Maybe someone slightly less senior and/or less famous, but still sufficiently established so that their LOR would matter? You probably attend classes of other professors, perhaps doing some sort of projects with some of them? Could it be expanded into a collaboration resulting in a publication or a research report?
Are there other TA/RA positions advertised? Or maybe someone is seeking an hourly-payed students to collect some data for their experiment? A professor is running a Math Society or a club?
You probably did your homework studying this professor really well, but sometimes the relations simply does not work out. Maybe he is not a very good person; maybe you could've been a little bit more delicate (or cautious) with the language you chose to make your inquires. Maybe you should've waited until the contract is signed before hinting your unhappiness with the arrangements. It is impossible to say at the moment; and there are more urgent matters pressing. The understanding will eventually come.
Many people adopt the strategy of "keeping your mouth shut" and are successful in academia. Many did not, and they are successful, too. Academia is diverse, and in parts it is still a place where academics are allowed to be weird and insubordinate as long as they deliver outstanding research and excellent teaching. But the flip side is of course that sometimes someone else is behaving inappropriately led by his/her ego, or a sense of entitlement, or simply as a result of heavy sleep deprivation, and you occasionally become a collateral damage. It is important to remember that we all are people and try to treat others in the same way you would like to be treated yourself.
If you are a student in the US, consider reaching out to your institution's ombuds services. They are usually an informal and neutral third party that can arbitrate disputes such as this. Although I can't elaborate on the terms of your termination (what does your contract say, are you at will?), knowing of this avenue of resolution may serve you well.