Actually, the metric variational definition for the stress-energy tensor (due to Hilbert, as remarked by Qmechanic) is an universal improvement procedure for the canonical stress-energy tensor (and hence not always concides with the latter), in a sense which will be made precise below. Such a procedure is necessary because the canonical stress-energy tensor, although always conserved, often fails to satisfy other physical requirements like gauge invariance (since it is an observable quantity), symmetry (needed if we want it to be a source for the gravitational field) and tracelessness (for locally scale invariant theories). For example, all three requirements fail for pure electrodynamics in four space-time dimensions.
Even if you are dealing with a field theory in Minkowski space-time, it is inevitably coupled to gravity simply because of the fact that the Lagrangian depends on the space-time metric (here taking the particular value of the Minkowski metric). The particular dynamics of the metric is irrelevant - all we need is that there are no other "external" fields besides the metric and that the field action functional is diffeomorphism invariant.
Let $L=L(\phi,g)$ be a local field Lagrangian in the space-time $(M,g)$, and $$S_K[\phi,g]=\int_K L(\phi,g)\sqrt{|\det g|}\mathrm{d}x\ ,\quad K\subset M\text{ any bounded region}$$ the corresponding (family of) action functional(s indexed by $K$ as above). We allow $L$ to have finite but otherwise arbitrary order dependence on $\phi$ and $g$, and no explicit space-time dependence since we want it not to depend on any other fields. The infinitesimal variation of $S_K$ with respect to a vector field $X$ on $M$ (i.e. an infinitesimal diffeomorphism) is then given by $$\delta_X S_K[\phi,g]=\int_K\left(\frac{\delta L(\phi,g)}{\delta g_{\mu\nu}}\delta_X g_{\mu\nu}+\frac{\delta L(\phi,g)}{\delta \phi^j}\delta_X \phi^j+\nabla_\mu(T^{\mu\nu}X_\nu)\right)\sqrt{|\det g|}\mathrm{d}x\ ,\quad X_\rho=g_{\rho\sigma}X^\sigma\ ,$$ where $\frac{\delta L(\phi,g)}{\delta g_{\mu\nu}}$ and $\frac{\delta L(\phi,g)}{\delta \phi^j}$ are respectively the Euler-Lagrange (i.e. variational) derivatives of $L(\phi,g)$ with respect to $g$ and $\phi$, $\nabla$ is the Levi-Civita covariant derivative associated to $g$, $T^{\mu\nu}$ is the (canonical or improved) stress-energy tensor, $$\delta_X g_{\mu\nu}=\nabla_\mu X_\nu+\nabla_\nu X_\mu$$ is the Lie derivative of $g$ along $X$ and the infinitesimal field variation $\delta_X\phi^j$ depends on the particular way we lift $X$ to a projectable vector field on the total space of the fiber bundle over $M$ where the fields $\phi^j$ live (for instance, if they are all scalar fields, we simply have $\delta_X\phi^j=-X\phi^j=-X^\mu\nabla_\mu\phi^j$).
There is an implicit but crucial requirement on the admissible improvements for $T^{\mu\nu}$ - namely, the improved Noether current $j^\mu(L,X)=T^{\mu\nu}X_\nu$ associated with the would-be symmetry $X$ of the action functional should not only be linear in $X$ but depend only on the point values of $X$ (we call this property ultralocality) - therefore, we wrote it already as a tensor contraction. This requirement also affects to a certain extent the definition of $\delta_X\phi^j$, but the details of this are not important in what follows. Why do we insist on this requirement? As we shall see below, ultralocality singles out a unique improvement prescription for $T^{\mu\nu}$ which in addition satisfies all physical desiderata. This idea applies more generally to any local symmetry - for instance, it may be used to improve the canonical Noether current associated with local gauge symmetries.
Diffeomorphism invariance of the action functional means we require that $\delta_X S_K[\phi,g]=0$ for all $X,\phi,g,K$. If, in addition, the fields $\phi^j$ satisfy the Euler-Lagrange equations of motion, we have that $$2\frac{\delta L(\phi,g)}{\delta g_{\mu\nu}}\nabla_\mu X_\nu+\nabla_\mu(T^{\mu\nu}X_\nu)=\left(2\frac{\delta L(\phi,g)}{\delta g_{\mu\nu}}+T^{\mu\nu}\right)\nabla_\mu X_\nu+X_\nu\nabla_\mu T^{\mu\nu}=0\ .$$ The first identity seems trivial but in fact follows from ultralocality of the improved Noether current, as explained above. Since $X$ is arbitrary and therefore we may specify $X_\nu$ and $\nabla_\mu X_\nu$ independently at each point of $M$, we obtain in a single stroke:
The desired variational formula for the improved stress-energy tensor $$T^{\mu\nu}=-2\frac{\delta L(\phi,g)}{\delta g_{\mu\nu}}$$ and therefore the symmetry $T^{\mu\nu}=T^{\nu\mu}$;
The covariant conservation law $\nabla_\mu T^{\mu\nu}=0$;
If the metric happens to obey a dynamics determined by a Lagrangian $L_G(g)$, then $T^{\mu\nu}$ automatically becomes the source to the metric equations of motion. This also guarantees compliance with the second Noether theorem, as it should - the canonical Noether current associated to the total (i.e. metric + field) Lagrangian and to $X$ still vanishes on shell if the total action functional is also diffeomorphism invariant.
Although it is not trivial to show, $T^{\mu\nu}$ also happens to be traceless if the field theory exhibits local scale invariance.
If the fields $\phi^j$ are all scalar and $L(\phi,g)$ is a Lagrangian of first order in $\phi$ with a Klein-Gordon-like kinetic part and not depending on derivatives of $g$, then $T^{\mu\nu}$ coincides with the canonical stress-energy tensor. This is no longer the case for spinor fields, whose Lagrangian usually also depends on the first derivatives of the metric through the spin connection, for scalar fields with non-minimal curvature coupling, or for the electromagnetic field.
The above understanding of the metric variational definition of the stress-energy tensor in full generality came surprisingly late - it was thoroughly developed by M. Forger and H. Römer ("Currents and the Energy-Momentum Tensor in Classical Field Theory: a Fresh Look at an Old Problem". Ann.Phys. 309 (2004) 306-389, arXiv:hep-th/0307199), whose work we warmly recommend for (many) more details and examples.
Best Answer
Most theories do not have a conserved energy-momentum tensor, regardless of whether they are Lagrangian or not. For example you need locality and Lorentz invariance. When you have those, you can define the energy-momentum tensor via the partition function (which always exists, it basically defines the QFT): $$ \langle T_{\mu\nu}\rangle:=\frac{\delta}{\delta g^{\mu\nu}}Z[g] $$ You can define arbitrary correlation functions of $T$ by including insertions. And these functions define the operator $T$ itself. So $T$ is defined whenever $Z$ is a (differentiable) function of the metric, i.e., when you have a prescription to probe the dependence of the theory on the background metric. And this prescription is part of the definition of the theory: in order to define a QFT you must specify how the partition function is to be computed, for an arbitrary background. If you cannot or do not want to specify $Z$ for arbitrary $g$, then the derivative cannot be evaluated and $T$ is undefined. (This is not an unreasonable situation, e.g. I may be dealing with a theory that is anomalous and is only defined for a special set of metrics, e.g. Kähler. This theory does not make sense for arbitrary $g$, so I may not be able to evaluate $Z[g]$ for arbitrary $g$, and therefore $T$ may not exist).
If the theory admits an action, then the dependence of $Z$ on $g$ is straightforward: it is given by whatever the path-integral computes. If the theory does not admit an action, then you must give other prescriptions by which to compute $Z$. This prescription may or may not include a definition for arbitrary $g$; if it does not, then $T$ is in principle undefined.
But anyway, for fun consider the following very explicit example: $\mathcal N=3$ supersymmetry in $d=4$. This theory is known to be non-lagrangian. Indeed, if you write down the most general Lagrangian consistent with $\mathcal N=3$ SUSY, you can actually prove it preserves $\mathcal N=4$ SUSY as well. So any putative theory with strictly $\mathcal N=3$ symmetry cannot admit a Lagrangian. Such a theory was first constructed in arXiv:1512.06434, obtained almost simultaneously with arXiv:1512.03524. This latter paper analyses the consequences of the anomalous Ward identities for all symmetry currents, in particular the supercurrent and the energy-momentum tensor.