Indeed, you can start from the Legendre transform because it is somewhat the saddle point of a Laplace transform which allows you to pass from the generating function/free energy (or entropy for the microcanonical ensemble) of an ensemble to an other.
(in the following I set $k_B$ to 1!)
Simple! Microcanonical to canonical
The microcanonical "free energy" is the entropy $S$, the canonical free energy is the usual Helmholtz free energy $F$. They are related through the following thermodynamics relation:
$$\beta F(\beta) + S(E) = \beta E \tag 1$$
Note that the Helmholtz free energy is a function of $\beta$ and the entropy is a function of $E$. Nonetheless, the Legendre transform explicitely gives a relation between $E$ and $\beta$. In any case, the partition function are the cumulant generating functions of the underlying distribution with "partition function" $$\Omega(E)=e^{S(E)} \text{ and } Z(\beta)=e^{-\beta F(\beta)}\tag 2$$
Note also the stupid factor $\beta$ appearing a bit everywhere or the "negative sign", they are relics of the old times of thermodynamics plaguing the formalism of statistical mechanics and preventing the maths to be particularly nice. Taking the exponential of (1) and using (2):
$$e^{-\beta F(\beta)}=e^{S(E)}e^{-\beta E}\to Z(\beta) = \Omega(E)e^{-\beta E}\tag 3$$
This looks like the relation between canonical and microcanonical except that you don't have the integral...
Here...
You might ponder why...
A little bit...
From now, we only used a thermodynamic relation (1), the Legendre transform which does not know anything about fluctuations. While we want to derive a statistical relation between ensembles. It is clear that we cannot do that only with a Legendre transform! And you can directly see it when we used the Legendre transform and said that $E$ really has to be understood as $E(\beta)$ or equivalently $\beta$ as $\beta (E)$ (from (1)). Indeed, we can rewrite, perhaps a little bit more clearly (3) as:
$$Z(\beta) = \Omega(E(\beta))e^{-\beta E(\beta)} \tag 4$$
If you compare that with the usual relation for the partition function:
$$Z(\beta) = \int d E'\Omega(E')e^{-\beta E'}\tag 5$$
It looks like that you have extracted only one value of the integral at $E' = E(\beta)$. And this is exactly what you did. You used a thermodynamic relation (1) which only care about mean value. It is equivalent to taking the saddle point of (5). In the thermodynamic limit ($N\to \infty$) the only contribution of the integral (5) is the maximum given by $\dfrac{d (\Omega(E')-\beta E')}{d E'}$ which is the Legendre transform (1). Thus $(4) = (5)$ but only in the thermodynamics limit.
To recapitulate (5) is the exact expression of the canonical partition function for any system size and is, by the way, a Laplace transform of the microcanonical partition function. In the thermodynamic limit, you recover (4) and thus (1) through a saddle point approximation of the Laplace transform (5).
Less trivial examples:
Of course, now, every different partition function can be found by "guessing" the Laplace transform that lead to the Legendre transform. For the NpT ensemble, the free energy is the Gibbs one $G$:
$$G(N, p, T)-F(N, V, T) = pV \text{ and } e^{-\beta G} = \Delta \to \Delta(p) = Z(V(p))e^{-\beta pV(p)} \tag 6$$
Again since we used a Legendre transform which is a thermodynamics relation, we don't have the integral, because we obtain a thermodynamic/$N\to\infty$/no fluctuation result. We then guess the Laplace transform which could have given this type of relation (this Legendre transform) through a saddle point. It is not so hard to guess that:
$$\Delta(p)=\int dV' Z(V')e^{-\beta p V'} \tag 7$$
Yet again, (6) follows from the saddle point of (7).
Finishing notes:
Of course, we did the opposite of what we should have done. You don't guess an equation :) The meaningful road to take is deriving the Legendre transform from the relations between the generating function. Not the opposite, however, this works well..
If you want to derive the relation you have, perhaps, a bit more rigorously, you would want to start from a system that you partition into two (like the usual microcanonical to canonical).
Edit: exact derivation of the ensembles.
From your comments it seems that you are interested also as to why the thing in the exponent changes from $E \rightarrow E + \text{something}$ as you change ensemble. It stems from the fact that you allow for new extensive variables to fluctuate, and hence, allow the system to perform work (with respect to the reservoir it is attached to).
For example, you assume that your system surrounded by a bath. You thus have two part. A large one that plays the role of a bath $B$. And a small one that is your system of interest $S$. The system exchanges some quantities with the bath (energy, particle, volume, surface, ...). If you assume that the thermodynamics of the systems under consideration is well defined and more importantly that it is extensive. You can simply write that the probability $P$ of observing the bath in some macrostate is given by the number of microstates compatible with the macrostate.:
$$P_{B} \propto \Omega_{B}(N_B, E_B, V_B, A_B, \dots) = \Omega_B(N_{tot} - N_S, E_{tot}-T_S, V_{tot} - V_S, A_{tot} - A_S)\tag 8$$
Where I took care of the differences between intensive and extensive variables and took some random thermodynamic values, I could have chosen different ones (I added $A$, the surface area of some membrane as an unusual example). Stating that the intensive variables are the same in $S$ and in $B$ is a big logical leap and should be better justified.
Since the size of the bath is way larger than the size of the system, we can expand $\log(\Omega_B)$ around the values $tot$ (we take the log for simplicity):
$$\log(P_B)=cst - N_S\left.\dfrac{\partial \log(\Omega_B(N))}{\partial N}\right|_{N = N_{tot}}- E_S\left.\dfrac{\partial \log(\Omega_B(E))}{\partial E}\right|_{E = E_{tot}}- V_S\left.\dfrac{\partial \log(\Omega_B(V))}{\partial V}\right|_{V = V_{tot}}- A_S\left.\dfrac{\partial \log(\Omega_B(A))}{\partial A}\right|_{A = A_{tot}}\tag 9$$
Now, you must input some thermodynamics into the mix. Adding that $\log(\Omega)=S$ and:
$$T\Delta S = \Delta E + p\Delta V - \gamma \Delta A- \sum_{i}\mu_i\Delta N_i - \sum_i F_i \Delta x_i\tag {10}$$
where $F_i$ are additional thermodynamic forces (like $P$, $S$ (already written explicitely), $\gamma$ or the magnetic field) an $x_i$ external control parameters (the conjugate of the forces: $V$, $T$, $A$ or the magnetization).
This gives you the derivative of the entropy with respect to the extensive variables and finally, you obtain (again assuming the equality of intensive variabbles throughout the system, which is not immediately given):
$$P_S = P_B\propto \exp\left({ - N_S\left.\dfrac{\partial S}{\partial N}\right|_{N = N_{tot}}- E_S\left.\dfrac{\partial S}{\partial E}\right|_{E = E_{tot}}- V_S\left.\dfrac{\partial S}{\partial V}\right|_{V = V_{tot}}- A_S\left.\dfrac{\partial S}{\partial A}\right|_{A = A_{tot}}}\right)\propto e^{\tilde S}\tag {11}$$
which together with (10) gives you the different exponent for different ensembles ($P_S=P_B$ follows from the fact that to one given microstate for $B$ corresponds one given microstate for $S$). Note that this is the probability of A microstate. For example, in the canonical ensemble, the probability of observing the microstate $i$ is proportional to $e^{-\beta E_i}$ where $E_i$ is the energy of the microstate $i$. However, the probability of observing a macrostate with energy $E$ is: $\Omega(E)e^{-\beta E}= e^{-\beta F(E)}$. More generally, the probability of observing a microstate is proportional to the exponential of some "microscopic" reduced entropy (in which we don't count the fixed extensive variables). while the probability of observing a value of a macrostate is proportional to a "microscopic" free energy of the ensemble.
