While I am of the opinion that David's deleted answer (involving free abelian categories) wasn't at all bad, and I'm sure fixable, here is another tack to take. It's a bit of a hack, but it should do the trick.
The rough idea is to "close up" the small graph '$G$' (see David's initial comment under the question) under all the abelian category operations, and expect to get a small abelian category. By "abelian category operations", I mean, in addition to categorical operations like composition, operations such as taking the direct sum of two objects, taking the kernel of a morphism, taking the cokernel of a morphism, and including a zero object (as constant or 0-ary operation). Technically, these might not be operations (in the sense that we might not have, e.g., chosen direct sums for each pair of objects, and also in the less bothersome sense that some of the operations might be only partially defined), and we'll have to address that below. But, if we do manage to find a small subcategory suitably closed under these "operations", it is immediate that the inclusion functor will be exact since kernels, cokernels, direct sums in the subcategory are chosen from among the kernels, cokernels, direct sums existing in the ambient large category. If we do it right, it will also be immediate that the abelian category axioms are satisfied in the small subcategory.
To do it right, we follow Categories, Allegories by Freyd-Scedrov, page 92, which suggests using the following definition:
An abelian category is a category with a zero object, biproducts, kernels, and cokernels such that for every morphism $x: A \to B$, the canonical map $coker(\ker(x)) \to \ker(coker(x))$ is an isomorphism.
For our purposes, it will be convenient to take a "morphisms-only" approach to category theory. Here a category is a class whose elements are thought of as morphisms, together with relations $s(f, h)$ ($h$ is a source of $f$ -- an object is defined to be a morphism that is a source of itself), $t(f, h)$ ($h$ is a target of $f$), $c(f, g, h)$ ($h$ is a composite of $f$ and $g$), together with a bunch of obvious axioms on these relations.
For abelian category theory as highlighted above, we additionally suppose given a zero object $0$ and a whole slew of tedious relations described as follows:
- $0_s(f, h)$ means $f$ is an object and $h$ is the unique morphism from $f$ to $0$;
- $0_t(f, h)$ means $f$ is an object and $h$ is the unique morphism from $0$ to $f$;
- $D_{i, 1}(f, g, h)$ means $f$, $g$ are objects and $h$ is the canonical injection of $f$ into a direct sum of $f$ and $g$;
- $D_{i, 2}(f, g, h)$ similarly means $h$ is the injection of $g$ into the direct sum;
- $D_{p, 1}(f, g, h)$, $D_{p, 2}(f, g, h)$ mean $h$ is a first or second projection map out of a direct sum of $f$ and $g$;
- $U_s(f, g, h)$ means $f$ and $g$ have a common target and $h$ is the corresponding map from a direct sum of their sources to that target, witnessing the universal property of coproducts;
- $U_p(f, g, h)$ is similar but for the universal property of products, dual to that for $U_s(f, g, h)$;
- $K(f, h)$ means $h$ is a kernel of $f$;
- $C(f, h)$ means $h$ is a cokernel of $f$;
- $U_k(f, x, h)$ means $f \circ x = 0$ and $h$ is the appropriate map from the source of $x$ to the source of a kernel of $f$, witnessing the universal property of kernels;
- $U_c(f, x, h)$ is similar but for the dual universal property of cokernels;
- $E(x, h)$ means $h$ is inverse to the canonical map $coker(\ker(x)) \to \ker(coker(x))$.
There are a whole bunch of axioms all these relations satisfy, all obvious from the verbal descriptions given. Notice we have consistently used the letter '$h$' for the last argument of each of these relations. The abelian category axioms assert in particular the existence of $h$ for each of these relations, given appropriate hypotheses on the other arguments. These existence axioms play the role of "axioms of closure" under "abelian category operations".
Assume that our $\mathcal{A}$ (as a class of elements in a universe or model of set theory $V$), and all of these abelian category relations on $\mathcal{A}$, are given by relations definable in ZFC, and assume there is a (small) set $S \subset \mathcal{A}$ of morphisms, that we want to generate a small abelian subcategory.
The punch line is that $S$ generates a set $T$ of morphisms which is closed under these relations, in the sense given in the following lemma.
Lemma: Let $\mathcal{A}$ be a class, and suppose $\theta_1, \ldots, \theta_k$ are relations on $\mathcal{A}$, with $arity(\theta_i) = n_i \geq 2$. Let $S \subseteq \mathcal{A}$ be any set. Then there is a set $T$ such that $S \subseteq T \subseteq \mathcal{A}$ and $T$ is "closed" under the $\theta_i$ in the sense that
$$\forall u \in T^{n_i - 1} (\exists_{x \in \mathcal{A}} \theta_i(u, x) \Rightarrow \exists_t t \in T \wedge \theta_i(u, t))$$
Proof: Consider the class $\mathcal{T}$ of labeled finite planar rooted trees$^1$, where the leaf nodes are labeled by elements of $S$, and where the non-leaf nodes are labeled by one of the symbols $\theta_{i}$. (If the tree consists of just a root, this is just labeled by an element of $S$.) This class is clearly a set. Let us further direct the edges so that there is a directed path from each leaf to the root (there is only one way to do this). This allows one to speak of the incoming edges and the outgoing edge at a node. There is no harm in drawing an outgoing edge sourced at the root, but without target.
Now consider the following subset $\mathcal{T}' \subseteq \mathcal{T}$ of what we call extendible trees. A tree is extendible if there is a way of labeling the edges by elements of $\mathcal{A}$ so that
The outgoing edge of a leaf has the same label as the leaf;
If the labels of the incoming edges of a node labeled $\theta_{i}$ are $x_1, \ldots, x_k$ (in that order, according to the planar structure) and the outgoing edge is labeled $x$, then $\theta_{i}(x_1, \ldots, x_k, x)$ holds.
An extendible tree together with a choice of such edge labelings will be called an extension of the extendible tree. An element that labels the outgoing edge at the root is called the output of the extension.
Proceeding by structural induction on the tree, choose an extension for each extendible tree. (Note: for those who are worried that at the inductive step there is a class of possible outputs to choose from, a standard workaround in ZFC might be to choose only from among elements of minimal ordinal rank within that class; see for instance Jech's Set Theory, page 68. The point is that there is only a set of such elements. This workaround is reminiscent of Scott's trick.) There is thus a set of chosen extensions.
We thus have a set $T$ of outputs, one for each chosen extension of an extendible tree. Suppose given $u = (u_1, \ldots, u_{n_i - 1}) \in T^{n_i-1}$ and suppose there exists $x$ such that $\theta_i(u, x)$. The $u_i$ are labels of outgoing edges at roots of a forest of chosen extensions, and their underlying extendible trees can be joined in a new extendible tree by adjoining a new root labeled $\theta_{i}$. By inductive construction, the chosen extension of this extendible tree has, at its root, incoming edges $u_i$ and output $t$. This $t$ belongs to the set of chosen outputs $T$, and we are done.
[1] Formally, a tree can be described as a functor $F: [n]^{op} \to \Delta$, where $[n]$ is a finite ordinal and $\Delta$ is the category of finite ordinals, such that $F(0) = [1]$.