I agree, but would it be so dramatic? One thing is almost certain: without de Gaulle, whatever Constitution is put together will not have a popularly elected Head of State, and in the long run, it might be a very good thing.
To make the Fourth Republic more efficient, one did not have to change everything. The reforms proposed by Félix Gaillard would have made the governments more stable. Get rid of proportional representation and adopt the 2-ballot majority system (as OTL's Fifth Republic did in 58) and you also reinforce ministerial stability and reduce the role of the political parties.
I think it is a mistake to consider that ONLY De Gaulle and ONLY the Fifth Republic could have saved the country from chaos in the early Sixties (and I do admire and respect Charles de Gaulle).
One last thing about OTL's Fifth Republic, established in 1958 and dramatically modified in 1962 by the popular election of the President. François Mitterrand used to say that the institutions were dangerous before him and would still be dangerous after him. When I look at what happened since our current President was elected, I think he was absolutely correct.
I totally agree. A form of consensus was forming in the late fifties to reform the parliamentary regime along the lines of the German "Kanzlersdemokratie" system, with more stable majorities supporting a designated Prime minister for the duration of the legislature, with the President being able to regulate the system with renewed arbitral powers (it was, notably, Mendès' proposal). The 1958 constitution, in itself, was not contradictory with this idea, and Debré actually considered that the exectuve powers should be primarily in the hand of the Governement, not the President. It, of course, changed after 1962, but, IMHO, not so much because of the direct election of the President than because of De Gaulle's extremely large intrepretation of the Constitution. After all, Austrian and Finnish presidents are also directly elected, and, constitutionnaly, I think that the Finnish president had as much power as the Ve Rep. President ; but they don't use it as extensively. The only limit to De Gaulle's power was his own integrity, since he left after his first lost referendum.
Assuming that Gaullists would have ended their move towards the IV Republic, I suppose that, after the end of the war, we would have a IV Republic Mk II roughly looking like the 1958 constitution, but with a weaker president. I think we wouldn't complain about it, from a constitutionnal point of view. (We wouldn't have the ridiculous caricature of the late Second Empire we're experiencing nowadays, at least)
As for the outcome of the Algerian war :
Military far-right coup : possible, but few chances of enduring success. You shouldn't underestimate the PCF capability of organizing a low-intensity guerilla war or terrorists attacks in the early stages. The coup would be backed by only a minority of people in France proper. I doubt that the US would be happy to have the central element (for logistical purposes, notably) of the western European defence system in turmoil.
Military victory in Algeria : also possible, since almost achieved in OTL. Absolutely useless, though, since the war was politically lost since at least 1956. At worst, bloody protacted war a la Portuguese and international isolation of France.
Political negotiations and Algerian independance : most probable solution, although the Prime minister, whoever he may be, will probably face assasination attempts.
The Rhodesian gambit : unlikely, but to so much. The European population in Algeria, with support from hard-line elements of the Army, secedes from France and establishes a French Algerian state, either on the whole territory or in Oranais, the most European-populated area. Would probably gain support from Francoist Spain and establish ties with Israel, South Africa, Taiwan, and so on.
As for Mollet, I guess he would have lost the SFIO leadership once the Algerian war comes to an end (the Parti Socialiste Autonome was created on an opposition to the war and to Mollet's support for De Gaulle's comeback), either in favour of Savary or Defferre. His Franco-British union idea (which was entierly personal and probably only half-serious) would have let the scene with him, provided, of couse, that it wasn't discarded after the Suez fiasco.Mitterrand would probably not have joined the SFIO, but a center-left coaltion led by the Radicals, who are more likely to survive in a revised Fourth.