Derivation of the Polyakov Action As is usually done when first presenting string theory, the Nambu-Goto Action,
$$
S_{\text{NG}}:=-T\int d\tau d\sigma \sqrt{-g}
$$
($g:=\det (g_{\alpha \beta})$ is the induced metric on the world-sheet and $T$ is a positive real number interpreted as the string tension), is introduced as the natural generalization of action for a relativistic point particle, which in turn is obviously a correct action as it produces the proper equations of motion (and has a nice geometric interpretation).
Not long after the introduction of the Nambu-Goto action, authors tend to introduce the Polyakov action,
\begin{align*}
S_{\text{P}} & :=-\frac{T}{2}\int d\tau d\sigma \, \sqrt{-h}h^{\alpha \beta}g_{\alpha \beta}=-\frac{T}{2}\int d\tau d\sigma \, \sqrt{-h}h^{\alpha \beta}\partial _\alpha X\cdot \partial _\beta X \\
& =-\frac{T}{2}\int d\tau d\sigma \, \sqrt{-h}h^{\alpha \beta}\partial _\alpha X^\kappa \partial _\beta X^\lambda G_{\kappa \lambda}(X),
\end{align*}
where $G_{\kappa \lambda}$ is the space-time metric, $g_{\alpha \beta}$ is the induced metric on the world-sheet, and $h_{\alpha \beta}$ is the auxiliary metric on the world-sheet ($h:=\det (h_{\alpha \beta})$).  They then usually proceed to show that these two actions are equivalent, in the sense that you can deduce the equations of motion for $S_{\text{NG}}$ given the equations of motion for $S_{\text{P}}$.
Now, that's all well and dandy, but that doesn't exactly show how one would actually arrive at the Polyakov action.  You can't make it as a theoretical physicist by mindlessly computing things to show you get the right answer; you have to be able to actually, you know, come up with things.  Hence, instead of just pulling the Polyakov action out of a hat, it would be nice to know a way of deriving or motivating the action.
So then, imagine you are handed $S_{\text{NG}}$ and you set out to come up with an equivalent action that, at the very least, doesn't involve a square-root.  How do you come up with the Polyakov action?
 A: The solution can be found in the article in here. The idea is, assume you have a starting action for an object whose extent is (spatially) $p$-dimensional. It can be described by introducing an auxiliary "abstract" worldvolume $\Sigma$ which will be embedded into spacetima via $X:\Sigma\rightarrow M$ of its worldvolume $\Sigma$ on $M$. Assume that it is described by the Nambu-Goto action
$$S(X)=-T\int\text{d}^{p+1}\xi\,\sqrt{-h},$$
where $h=X^*G$ is the induced metric and $G$ is the metric on $M$. Being written in terms of purely geometric objects, this action is invariant under diffeormorphisms of $\Sigma$. This should be the case since this space was auxiliary.
Now, just to make a sensible story, let us assume that we want to build a toy model of gravity by placing an intrinsic metric $g$ on $\Sigma$ which describes the theory above. A systematic solution to this problem is to consider the same action with the added constraint that forces $g=h$. This takes the form
$$S(X,g,\Lambda)=-T\int\text{d}^{p+1}\xi\,\left(\sqrt{-g}+\Lambda^{ab}(h_{ab}-g_{ab})\right),$$
for some Lagrange multiplier $\Lambda$ which is a density valued tensor product of two vectors. Clearly the equations of motion obtained by varying the Lagrange multiplier yield the constraint we wanted and plugging this back in we obtain the Nambu-Goto action.
A different route however is obtained by instead considering the equations of motion obtained by varying the intrinsic metric we obtain
$$\frac{1}{2}\sqrt{-g}g^{ab}=\Lambda^{ab}.$$
Plugging this back in we obtain the Polyakov action
$$S(X,g)=-\frac{T}{2}\int\text{d}^{p+1}\xi\,\sqrt{-g}\left(g^{ab}h_{ab}+1-p\right).$$
In particular, for the string $p=1$ and we obtain the usual Polyakov form.
To people interested, I really recommend the article cited. It also has a nice method of obtaining actions that are Weyl invariant.
I was very sad to hear about the passing of the OP. I have found his involvement on this site and his writings very useful throughout my studies.
A: 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.
A: Quantum systems are essentially defined by their symmetries. For example, in QFT's you expect all terms not forbidden by the symmetries of the problem to appear in the Lagrangian, with irrelevant operators suppressed by large scales, etc. 
So I think your first step in this approach would be to write down the most general 2D QFT respecting the 2D Diff and internal Poincare symmetries. The Diff symmetry motivates you to introduce a dynamical metric, since you've already done a similar thing for the point particle. This doesn't quite get you to the Polyakov action, since the Polyakov action has a Weyl symmetry that the NG action doesn't. You've introduced a fake degree of freedom on the worldsheet that wasn't present in the NG action, so you need some local symmetry principle to remove the redundant degrees of freedom. I don't know of a particular way to reason that this symmetry has to be Weyl invariance, maybe someone else does. 
But once you believe the theory should have a local lagrangian with Diff, Poincare and Weyl symmetries, you are basically stuck with the Polyakov action. The Polyakov action (with the Euler characteristic term) is the most general 2D action with the Diff, Poincare and Weyl symmetries and the associated field content (Polchinski p 15 ). 
So the guiding principle should be the symmetries of the NG action.
A: Maybe you are missing a fundamental most basic point here. Your argument I believe, is something along the lines "how can one make up actions for specific theories to get the equations of motion?". This is not how it works. The action comes from the Lagrangian which represents the dynamics of the system. The Lagrangian is then integrated over all dimensions. THIS is what (is) gives the ACTION. It is not "just pulled out of the air", but from the dynamics of the system. Ie. from tangible, real physical states of affairs.
