The Controlled Substances Act of 1970 provides two ways for a substance to be rescheduled. One is by congressional action, which has been attempted, e.g., in a bill authored by Barney Frank and Ron Paul. It can also be done by a rule-making process through HHS and DEA, but this petition process is extremely slow and, although it has been tried multiple times, has never succeeded. The HHS-DEA process involves the Justice Department and HHS, both of which are part of the executive branch.
The president does not really have unlimited power to force the Justice Department and HHS to do things. The Justice Department is a law-enforcement organization, and there is traditionally somewhat of a firewall between it and the oval office. Most presidents understand this, and are loath to micromanage things like the disposition of specific criminal cases.
It is true that the current lack of federal prosecution for simple possession of marijuana has been based on executive orders. However, this is a matter of discretion in prosecution over a broad category of cases, but it doesn't overrule the entire structure set up by the CSA or, e.g., make it legal for banks to take marijuana money.
If a president wanted to use executive-branch action to reschedule marijuana, then I don't think he would realistically either need to, nor would it suffice to, threaten some kind of Saturday night massacre at the DoJ. He would simply campaign on it, pick nominees for AG and HHS who supported it, and then the next time a petition was going through the rule-making process, they would manage the process in such a way that it would succeed, although it could take five or ten years to complete.
Before doing something like this, I think he would realistically also need to get Congress on board. Otherwise they could simply reverse him legislatively.
I don't think rescheduling would have any effect on state laws that still make recreational marijuana illegal in 32 states. Nor is rescheduling the same as legalization.