I) The closest cosmetic resemblance between the Nambu-Goto action and the Polyakov action is achieved if we write them as
$$\tag{1} S_{NG}~=~ -\frac{T_0}{c} \int d^2{\rm vol} ~\det(M)^{\frac{1}{2}} , $$
and
$$\tag{2} S_{P}~=~ -\frac{T_0}{c}\int d^2{\rm vol}~ \frac{{\rm tr}(M)}{2} , $$
respectively. Here $h_{ab}$ is an auxiliary world-sheet (WS) metric of Lorentzian signature $(-,+)$, i.e. minus in the temporal WS direction;
$$\tag{3} d^2{\rm vol}~:=~\sqrt{-h}~d\tau \wedge d\sigma$$
is a diffeomorphism-invariant WS volume-form (an area actually);
$$\tag{4} M^{a}{}_{c}~:=~(h^{-1})^{ab}\gamma_{bc} $$
is a mixed tensor; and
$$\tag{5} \gamma_{ab}~:=~(X^{\ast}G)_{ab}~:=~\partial_a X^{\mu} ~\partial_b X^{\nu}~ G_{\mu\nu}(X) $$
is the induced WS metric via pull-back of the target space (TS) metric $G_{\mu\nu}$ with Lorentzian signature $(-,+, \ldots, +)$.
Note that the Nambu-Goto action (1) does actually not depend on the auxiliary WS metric $h_{ab}$ at all, while the Polyakov action (2) does.
II) As is well-known, varying the Polyakov action (2) wrt. the WS metric $h_{ab}$ leads to that the $2\times 2$ matrix
$$\tag{6} M^{a}{}_{b}~\approx~\frac{{\rm tr}(M)}{2} \delta^a_b~\propto~\delta^a_b $$
must be proportional to the $2\times 2$ unit matrix on-shell. This implies that
$$\tag{7} \det(M)^{\frac{1}{2}} ~\approx~ \frac{{\rm tr}(M)}{2},$$
so that the two actions (1) and (2) coincide on-shell, see e.g. the Wikipedia page. (Here the $\approx$ symbol means equality modulo eom.)
III) Now, let us imagine that we only know the Nambu-Goto action (1) and not the Polyakov action (2). The only diffeomorphism-invariant combinations of the matrix $M^{a}{}_{b}$ are the determinant $\det(M)$, the trace ${\rm tr}(M)$, and functions thereof.
If furthermore the TS metric $G_{\mu\nu}$ is dimensionful, and we demand that the action is linear in that dimension, this leads us to consider action terms of the form
$$\tag{8} S~=~ -\frac{T_0}{c}\int d^2{\rm vol}~ \det(M)^{\frac{p}{2}} \left(\frac{{\rm tr}(M)}{2}\right)^{1-p} , $$
where $p\in \mathbb{R}$ is a real power. Alternatively, Weyl invariance leads us to consider the action (8). Obviously, the Polyakov action (2) (corresponding to $p=0$) is not far away if we would like simple integer powers in our action.
The path integral involving the Nambu-Goto square root in the exponent is a very complex animal. Especially in the Minkowski signature, there is no totally universal method to define or calculate the path integrals with such general exponents.
So if you want to make sense out of such path integrals at all, you need to manipulate it in ways that are analogous to the transition from Nambu-Goto to Polyakov. The fact that these transitions are justified classically or algebraically is a reason to say that you are giving a reasonable definition to the Nambu-Goto path integral.
If you hypothetically had different values of the Nambu-Goto path integrals (and Green's functions), you could still try to perform the steps, the introduction of the additional $h_{ab}$ auxiliary metric, and the transformations to obtain the Polyakov form. So if there were some other value of the Nambu-Goto path integral, there would have to be a way to see it in the Polyakov variables, too.
But the Polyakov path integral is much more well-behaved (also renormalizable, anomaly-free in $D=26$ etc.), especially when you fix the world sheet metric $h_{ab}$ to a flat or similarly simple Ansatz. The Polyakov path integral is pretty much unambiguous and well-behaved which is why there can't be any other reasonable result coming out of it, and because of the relationship with the Nambu-Goto action, there can't be any other meaningful enough meaning of the Nambu-Goto path integral, either.
I think that instead of asking whether two well-defined objects are the same, the right attitude to this question is to admit that the Nambu-Goto path integral (or quantum theory based on it) is a priori ill-defined, a heuristic inspiration, and we're trying to construct a meaningful well-defined quantum theory out of this heuristic inspiration. And the transition to the Polyakov-like calculus isn't just an option, it's pretty much an unavoidable step in the construction of a quantum theory based on the Nambu-Goto heuristics.
Best Answer
I) OP is asking for a direct/forward derivation from the Nambu-Goto (NG) action to the Polyakov (P) action (as opposed to the opposite derivation). This is non-trivial since the Polyakov action contains the world-sheet (WS) metric $h_{\alpha\beta}$ with 3 more variables as compared to the Nambu-Goto action.
Although we currently do not have a natural forward derivation of all 3 new variables, we have for 2 of the 3 variables, see section IV below.
II) Let us first say a few words about the derivation of the relativistic point particle
$$ L~:=~\frac{\dot{x}^2}{2e}-\frac{e m^2}{2}\tag{1} $$
from the square root Lagrangian
$$L_0~:=~-m\sqrt{-\dot{x}^2}.\tag{2} $$
Note that OP's derivation does not explain/illuminate the fact that the einbein/Lagrange multiplier
$$ e~>~0\tag{3}$$
can be taken as an independent variable, and not just a trivial renaming of the quantity $\frac{1}{m}\sqrt{-\dot{x}^2}>0$. It is an important property of the Lagrangian (1) that we can vary the einbein/Lagrange multiplier (3) independently. OP's request to not use Lagrange multipliers seems misguided, and we will not follow this instruction.
III) It is possible to directly/forwardly/naturally derive the Lagrangian (1) with its Lagrange multiplier $e$ from the square root Lagrangian (2) as follows:
Derive the Hamiltonian version of the square root Lagrangian (2) via a (singular) Legendre transformation. This is a straightforward application of the unique Dirac-Bergmann recipe. This leads to momentum variables $p_{\mu}$ and one constraint with corresponding Lagrange multiplier $e$. The constraint reflects world-line reparametrization invariance of the square root action (1). The Hamiltonian $H$ becomes of the form 'Lagrange multiplier times constraint': $$H~=~\frac{e}{2}(p^2+m^2).\tag{4} $$ See also e.g. this & this Phys.SE posts.
The corresponding Hamiltonian Lagrangian reads $$\begin{align} L_H~=~&p \cdot \dot{x} - H\cr ~=~&p \cdot \dot{x} - \frac{e}{2}(p^2+m^2).\end{align} \tag{5} $$
If we integrate out the momentum $p_{\mu}$ again (but keep the Lagrange multiplier $e$), the Hamiltonian Lagrangian density (5) becomes the sought-for Lagrangian (1). $\Box$
IV) The argument for the string is similar.
Start with the NG Lagrangian density $${\cal L}_{NG}~:=~-T_0\sqrt{{\cal L}_{(1)}}, \tag{6}$$ $$\begin{align} {\cal L}_{(1)}~:=~&-\det\left(\partial_{\alpha} X\cdot \partial_{\beta} X\right)_{\alpha\beta}\cr ~=~&(\dot{X}\cdot X^{\prime})^2-\dot{X}^2(X^{\prime})^2~\geq~ 0. \end{align}\tag{7}$$
Derive the Hamiltonian version of the NG string via a (singular) Legendre transformation. This leads to momentum variables $P_{\mu}$ and two constraints with corresponding two Lagrange multipliers, $\lambda^0$ and $\lambda^1$, cf. my Phys.SE answer here. The two constraints reflect WS reparametrization invariance of the NG action (6).
If we integrate out the momenta $P_{\mu}$ again (but keep the two Lagrange multipliers, $\lambda^0$ and $\lambda^1$), the Hamiltonian Lagrangian density for the NG string becomes $${\cal L}~=~T_0\frac{\left(\dot{X}-\lambda^0 X^{\prime}\right)^2}{2\lambda^1} -\frac{T_0\lambda^1}{2}(X^{\prime})^2,\tag{8}$$ cf. my Phys.SE answer here.
[As a check, if we integrate out the two Lagrange multipliers, $\lambda^0$ and $\lambda^1$, with the additional assumption that $$\lambda^1~>~0\tag{9}$$ to avoid a negative square root branch, we unsurprisingly get back the original NG Lagrangian density (6).]
Eq. (8) is as far as our forward derivation goes. It can be viewed as the analogue of our derivation for the relativistic point particle in section III.
Now we will cheat and work backwards from the Polyakov Lagrangian density
$$\begin{align} {\cal L}_P~=~&-\frac{T_0}{2} \sqrt{-h} h^{\alpha\beta} \partial_{\alpha}X \cdot\partial_{\beta}X\cr ~=~&\frac{T_0}{2} \left\{\frac{\left(h_{\sigma\sigma}\dot{X}- h_{\tau\sigma}X^{\prime}\right)^2}{\sqrt{-h}h_{\sigma\sigma}} - \frac{ \sqrt{-h}}{h_{\sigma\sigma}}(X^{\prime})^2 \right\} .\end{align} \tag{10}$$