Yes he could. The biggest issue with the late Abbasid house was their ineffective political skills. Previous Abbasid rulers often where politically competent and could at least hold semblances of power against Mu'Tazalite advisors and Mamluk guards and generals. However post 1300 Abbasid caliphs did not display any such skill politically and often were content to remain in positions where benefit was gained with the least gamble.
As well, a major issue with al-Musta'in Billah was who he surrounded himself with. Within Egypt, at this period, the Abbasid caliphs in order to stay in power must make extreme overtures to the Ulama and their constituents and attempt to curtail the power of Mamluks and millitary personel. The reason for this, is that the Ulama of this period were the only major force that absolutely wishes for a return to the Abbasid throne and in the same breath have a disdain for many Mamluks and have the ear of foreign rulers and the peasantry in many cases.
This thus becomes enormously difficult when you realize that the sultans have no army of any sort to defend the Caliph nor do they have anything beyond influence. Though, more auspicious events have occurred, most famously how the Ulema repelled Timur from the Mamluks by invoking their takfir and critiquing Timur.
So, I propose perhaps a skeleton of how Musta'in Billah could possibly build an effective base.
1. Invite and surround himself with critical thinkers and Ulema, those who have knowledge of history and economics especially. Ibn Hajar and al-Maqrizi would be examples of perfect Ulema for positions around him. Maqrizi for example was a staunch supporter of the Caliphate and was a somewhat opposed to many of the excesses of the Mamluks of the Burji. Some scholars also believed Maqrizi was a descendant of the Fatimid house; none can know for sure however.
2. Begin to quickly build a base of support amongst Zahri and other legalistic and strict Shaykhs, tribes and peasants throughout the area. With the intention of massacring or trapping the Mamluks. With Caliphal authority and alliances of Ulema, this may actually be possible, especially with a number of loyal Mamluks.
3. Gain foreign support. Send envoys to all surrounding Islamic states seeking recognition and friends among them. This could include a tribute of soldiers or treasure as Musta'in Billah received. Recognition of his rule would increase his chances of victory if his plan fails and instead of wiping the Mamluks out in a swoop, instead has to battle them directly. Intervention from Naaruz in Syria then becomes probable as is with other neighboring states seeking to gain legitimacy by being a defender of the Abbasid throne.