Full and Faithful can be easily defined in general with no reference to Set.
Just state:
Faithful functor F
$\forall (f,g: A \to B)$: $Ff = Fg$ implies $f = g$
Full functor F
$\forall (h: FA\to FB)$ $\exists (f: A \to B):Ff = h$
Just FOL, no set theory or category of sets.
You can find this in CWM chapter 1 section Functors
$\DeclareMathOperator{\im}{im}$
One rather abusive way of solving this problem is as follows. Consider $f : W \to C'$ s.t. $c \circ f = 0$. Take the least full subcategory containing $W$ and the above diagram which is closed under finite products, kernels, and cokernels. Assuming the abelian category is locally small, the full subcategory will be a small abelian category. Then, one may apply the Mitchell Embedding Theorem.
There is even a complicated way of getting around the largeness of the category based on the completeness of first-order logic and the fact that every consistent theory has a small model. If it were logically consistent that $c$ is not monic, then because the entire situation can be expressed in first-order logic, there would be a small Abelian category in which we would have $c$ not monic. But in the small case, we can apply the Mitchell Embedding Theorem. Thus, it must be logically inconsistent that $c$ is not monic - that is, there must exist some first-order logic proof that $c$ is monic. This guarantees that if you look around enough, you'll eventually find a proof that $c$ is monic in the general case.
Edit: original poster wants to avoid the embedding theorem, so I've added an explanation of how to do that.
First, let's walk through the proof in the case of $R-mod$.
Consider some $f : W \to C'$ s.t. $c \circ f = 0$. We wish to show that $f = 0$.
We have $d \circ \gamma' \circ f = \gamma \circ c \circ f = 0$. Thus, $\gamma' \circ f = 0$. Therefore, $f$ factors through $\ker(\gamma')$.
Now, consider some $x \in W$. Since $f(x) \in \ker(\gamma') = \im(\beta')$, we may take $y \in B'$ s.t. $\beta'(y) = f(x)$.
We have $\beta(b(y)) = c(\beta'(y)) = c(f(x)) = 0$. Then $b(y) \in \ker(\beta)$.
Since $b(y) \in \ker(\beta) = \im(\alpha)$, take $z \in A$ s.t. $\alpha(z) = b(y)$.
Since $a$ is epi, it is surjective. Thus, we may take $w \in A'$ s.t. $a(w) = z$.
$b(\alpha'(w)) = \alpha(a(w)) = \alpha(z) = b(y)$. Therefore, $\alpha'(w) = y$.
Since $y = \alpha'(w)$, we have $y \in \im(\alpha') = \ker(\beta')$. Therefore, $f(x) = \beta'(y) = 0$.
Then $f = 0$. Thus, $c$ is monic.
Now, let's think about how to generalise this proof to hold in an arbitrary Abelian category.
Clearly, steps 1-2 generalise flawlessly. The real challenge is to generalise steps the other steps. Consider the following revised proof, starting with step 3. The trick is that every time we introduce a new variable (w, y, and z), we replace this by forming a pullback.
We abusively write $f : W \to \ker(\gamma') = \im(\beta')$, $\beta' : B' \to \im(\beta')$. Then we may form the pullback $P = \{(x, y) : f(x) = \beta'(y)\}$ with morphisms $p_1 : P \to W$, $p_2 : P \to B'$. Since $\beta' : B' \to \im(\beta')$ is surjective (epi), so too is its pullback $p_1$. Thus, it suffices to show that $f \circ p_1 = 0$; that is, to show that $\beta' \circ p_2 = 0$.
We have $\beta \circ b \circ p_2 = c \circ \beta' \circ p_2 = c \circ f \circ p_1 = 0$. That is, $b \circ p_2$ factors through $\ker(\beta)$.
We may again abusively write $b \circ p_2 : P \to \ker(\beta) = \im(\alpha)$ and $\alpha : A \to \im(\alpha)$. Then we may form the pullback $Q = \{(p, z) : \alpha(z) = b(p_2(p))\} = \{((x, y), z) : \alpha(z) = b(y)$ and $\beta'(y) = f(x)\}$ with morphisms $q_1 : Q \to P$ and $q_2 : Q \to A$. Since $\alpha : A \to \im(\alpha)$ is epi, so too is its pullback $q_1$.
We repeat this trick one more time to produce the pullback $R = \{(q, w) : q_2(p) = a(w)\}$ and morphisms $r_1 : R \to Q$, $r_2 : R \to A$. Since $a$ is epi, so too is its pullback $r_1$.
We have $b \circ \alpha' \circ r_2 = \alpha \circ a \circ r_2 = \alpha \circ q_2 \circ r_1 = b \circ p_2 \circ q_1 \circ r_1$. Since $b$ is monic, we have $\alpha' \circ r_2 = p_2 \circ q_1 \circ r_1$.
Therefore, we have $\beta' \circ p_2 \circ q_1 \circ r_1 = \beta' \circ \alpha' \circ r_2 = 0$. Since $q_1$ and $r_1$ are epi, we have $\beta' \circ p_2 = 0$.
We discussed in step 3 that this implies $f = 0$. Then $c$ is monic.
Hopefully, my revised steps 3-8 make it clear how to deal with the problem in the general setting of Abelian categories. The only nontrivial fact we really need is that pullbacks of epis are epi in Abelian categories.
Best Answer
Using the axiom of choice, you can prove that epimorphisms (surjections) split in $\mathbf{Set}$, meaning that if $f \colon A \to B$ is epic, then there exists $g \colon B \to A$ such that $f \circ g = \text{id}_B$. From there, you just need to prove that functors preserve split epimorphisms.
The corresponding statement for monomorphisms isn't true (see this question). However, monomorphisms with non-empty domain split, so the same proof would work for those.