How to find new advisor after being let go
The way to find a new advisor is to ask. Whether they say yes depends on many things, including the known behavior of your current advisor. Are they reasonable or not? Is it you or is it the advisor who is the problem here?
You should also look at why you are having difficulties. Is the problem you are working on just too hard. This can happen in mathematics, for example, and it may take years to get partial results. Or the problem may even be unsolvable at the current state of knowledge, or even unresolvable in theory. If your have an impossible problem then a new advisor with a new problem would possibly work.
When you apply make the best case that you can be a success and get the best letters available to you. Your current advisor might write a good letter or not, but that depends on circumstances. Are you being let go because you aren't up to it, or because the demands of the research program of the advisor demand faster results. That might be the case in some lab sciences.
But in the end, all you can do is ask and apply and make the best case you can. Stress successes you have had, not failures.
It may well be that working harder to meet the deadline is a possibility. That would probably be the shortest path to success if you can manage it.
But any other path will take time. Be prepared for that and examine and evaluate all of your options.