The basic problem is that the holes must radiate. The result is a completely asymmetrical spacetime that cannot be attacked analytically. There are a few ways around this.
You can use the post-Newtonian expansion. Here, GR is formulated as a series of corrections to Newtonian gravity in powers of $\frac{v}{c}$. The expansion is now known to very high order and remains integrable. It seems to give quite accurate results.
You can integrate the EFEs numerically. This is possible because, while entire binary spacetimes are very difficult to find analytically, it is still possible to find families of solutions modelling a single spacelike hypersurface of such spacetimes. In principle, since GR has a formulation as an initial value problem, it is then possible to integrate forward for as long as you want. Even if the initial slice isn't especially realistic, the no hair theorems give some comfort that after a quick relaxation period during which the unphysical deformations get released as "junk radiation", the actual inspiral becomes generic. Actually performing the simulations is very difficult for a number of reasons: the first binary black hole inspiral and merger was not successfully completed until 2006.
You can perturb around an exact black hole solution. This is the goal of the so-called "self-force" program. The idea is that the smaller black hole should deform the 'background' metric in a way analogous to the electromagnetic radiation reaction, or the QED self-energy. This turns out to be really hard to do in practice, although some progress has been made for Schwarzschild backgrounds.
You can construct a few highly unphysical solutions with multiple black holes. These typically have some kind of bizarre feature that somehow holds the holes in place. For example this paper http://iopscience.iop.org/article/10.1088/0264-9381/31/22/225009;jsessionid=CC35FAD5AE9913F094348033E0C4776D.c2.iopscience.cld.iop.org studies a pair of black holes held rigidly in place by an extremely pathological "cosmic string". Another possibility is to feed in gravitational radiation from infinity in such a way as to \emph{exactly balance} the radiation reaction, cancelling the inspiral. I'm not sure whether an exact solution exists for the latter case, but if the holes co-rotate you do get back at least one Killing vector (corresponding to a "helical" symmetry).