First, there is no mechanical algorithm to solve a general differential equation. Einstein's equations are obviously no exception – in fact, they belong among the more complicated and less "solvable" equations among those one may learn about. Analytically writable solutions only exist in very special, simple, and/or symmetric cases (simple enough equations describing simple enough physical situations).
Second, Einstein's equations don't determine the metric uniquely. Even with well-defined initial/boundary conditions, they only determine the solution (metric tensor field) up to a general coordinate transformation (which may be determined by 4 functions $X^\mu(x^\nu)$ of the old coordinates). It means that out of the 10 components of the symmetric metric tensor, only 6 functions are really independently physical. When we impose 4 "gauge-fixing" conditions on the metric tensor field, we effectively define the "right" coordinates and we are left with 6 independent equations for the remaining 6 functions that determine the metric tensor as a function of the coordinates. Einstein's equations are superficially 10 equations but 4 of them (more precisely 4 equations constructed out of the derivatives of these equations and the equations themselves), the covariant divergence $\nabla_\mu (G^{\mu\nu} - K\cdot T_{\mu\nu})=0$, are obeyed identically so they don't constrain the metric.
Third, general relativity may also contain point masses, the point-like sources of the gravitational field that indeed add a delta-function of a sort to the metric tensor. If that's so, general relativity is a coupled system of mutually interacting Einstein's partial differential equations and ordinary differential equations for the world lines which may be parameterized e.g. by $t(x^i)$ or otherwise (e.g. using an auxiliary time parameter along the world line – which requires us to deal with a one-dimensional coordinate transformation redundancy analogous to the four-dimensional above). Alternatively, matter may be described by electromagnetic, Klein-Gordon, Dirac, and other fields. In that case, we deal with a coupled system of many partial differential equations – Einstein's equations plus Maxwell's equations plus the Dirac equation(s) and Klein-Gordon equation(s) with various source terms.
In practice, given a stress-energy tensor $T_{\mu\nu}$, we may attempt to find solutions to the Einstein field equations using perturbation theory. The basic idea is to expand around a known solution $g_{\mu\nu}$ by a perturbation $h_{\mu\nu}$. In the case of a flat background,
$$\delta G_{\mu\nu} = 8\pi G \delta T_{\mu\nu} = \partial_\mu \partial_\nu h - \partial_\mu \partial_\alpha h^\alpha_\nu -\partial_\nu \partial_\alpha h^\alpha_\mu + \partial_\alpha \partial^\alpha h_{\mu\nu} - \eta_{\mu\nu} \partial_\alpha \partial^\alpha h + \eta_{\mu\nu} \partial_\alpha \partial_\beta h^{\alpha \beta}.$$
In some cases, one may solve the equations exactly, or more typically, employ numerical methods. Another alternative approach when faced with a stress-energy tensor is to try to determine the symmetries the metric may have, and then plug in an ansatz for the metric to yield a set of differential equations which may be more tractable, analytically and numerically.
Yet another alternative is to generate new solutions from old ones through the introduction of pseudopotentials, a method due to Harrison, Eastbrook and Wahlquist, called the method of prolongation structures.
There are several other methods such as those that rely on Lie point symmetries of differential equations. There is also a Backlund transformation, which relies on identifying a simpler differential equation whose solution satisfies a condition involving the solution to the harder problem.
These methods are too involved to present here and require a significant background. They are explained in Exact Solutions to the Einstein Field Equations by H. Stephani et al.
Addressing your other question, if given a metric $g_{\mu\nu}$, of course one can compute $T_{\mu\nu}$ through the Einstein field equations, you just plug it in and tediously compute all the curvature tensors. There are strictly speaking probably some requirements on the functions in $g_{\mu\nu}$, but you can get away with most things, even distributions, such as a delta function, which may lead to a stress-energy tensor describing a brane.
Best Answer
When Einstein derived his equations the Newtonian limit (and it may be taken also in the present of sources) was an important check for the theory. It is also useful to understand the limits of the Newtonian theory, and sometimes helps to work out the intuition about the relativistic case.
However to solve Einstein equations the Newtonian limit is not required and sometimes is not useful at all.
First, there are exact solutions of the Einstein equations: various black holes and the sufficiently symmetric stars, the cosmological solutions and some other situations. Second, you may use the perturbation theory near the exact solutions. The simplest such application is linearized gravity that describes gravitational waves on a flat Minkowski background. Note that contrary to your original post, this weak gravity limit is not Newtonian. The gravitational waves do not exist in the Newtonian theory.
Third, you may use the Newtonian limit and start with the Poisson equations. Then you may perturb this solution adding relativistic effects. This is,obviously, a method depending on the Newtonian theory. It is known as a post-Newtonian expansion and is different from a weak gravity limit.
You may also solve the Einstein equations numerically. This is e.g. is used to study the black hole collisions where different perturbation theories fail. This is also a situation where the Newtonian theory is useless.