It's provided for under the Constitution Act, 1982, which states that authority to amend the Constitution is exercised through five types of procedures, each of which involves different actors.
So as regards the part of the question concerning New Brunswick, my answer is that the bilingualism guarantees that, I believe, are provided under section 16.1 of the Constitution Act, 1982, and that have become applicable relatively recently, in the 1990s, were adopted with the consent of the federal government and can only be amended together with it, and the same is true of the guarantees afforded to Quebec anglophones under section 133. Consequently, New Brunswick and Quebec can't exercise their autonomy with regard to constitutional amendments to the same extent as in the scenario you describe.
Saying that Quebec's only official language is French may obviously raise concerns, but, in real terms, you have to read this section as though it means the following: subject to the rest of the Constitution and the rights expressly named in section 133, Quebec's common and official language is French. These provisions must therefore be reconciled with each other. Quebec definitely can't amend them unilaterally.