Getting letters of recommendation for a master's degree if I don't get along with my current advisor
A few points regarding your questions:


Presenting a weak conference paper is only very slightly better than presenting no paper at all. It may even be worse, if someone evaluating your application saw the presentation and came away unimpressed.
There is no requirement that you get a letter from someone like your present advisor. Such a relationship is clearly not productive for either of you, and including a letter would definitely not help.
You do need to get letters from people who can comment on your work skills, so your old advisor would be acceptable. Other people with whom you have worked—so long as it's technical in origin, even if it's not explicitly research—could also write letters for you. If you can't get three such letters, then you should get them from people who know you beyond taking classes with them. Only if you exhaust all other possibilities should you rely on people who know you only from classwork.
Finally, find yourself a new advisor, if at all possible.