Definitions
Congruence (Internal Equivalence Relation): please refer to the following n-lab article: congruence
Finest congruence for a given parallel morphisms $f_1, f_2:A\rightarrow B$ is a congruence $(E, p_1, p_2)$ such that 1. $(f_1, f_2)$ factors through it, and 2. Given any congruence $(E', p_1', p_2')$ through which $(f_1, f_2)$ factors, $(E, p_1, p_2)$ factors through $(E', p_1', p_2')$ as well.
Context
A category $C$ with binary products, equalizers, and co-equalizers.
Question
Consider a pair of parallel maps $f_1, f_2:X\rightarrow A$ and their coequalizer $eq^*:A\rightarrow E^*$. One can show that the equalizer of pair $(eq^{*}\circ \pi_1, eq^{*}\circ \pi_2)$ (Where $\pi_1$ and $\pi_2$ are projections $A^2\rightarrow A$) gives us a congruence $(E, \pi_1\circ eq, \pi_2\circ eq)$ through which $(f_1, f_2)$ factors. However, I am stuck at proving that it is also the finest congruence there is in $C$. I tried assuming that the finest congruence exists, but then again I was unable to show that it is isomorphic to $(eq^{*}\circ \pi_1, eq^{*}\circ \pi_2)$. I am not sure how to proceed. Any help/comment will be great.
Disclaimer I'm not sure where you got this from, or even if this is true in the generality you've stated. What follows is most of a proof, with some sketchy parts that need filling in. The difficulty here in proving this is that you need to produce a morphism out of an equalizer, which is hard. This is therefore a partial answer.
I'm going to do my best to draw the diagrams, but we have limited commutative diagram facilities here. Parallel morphisms in particular can't be represented, so I'll label an arrow with two labels when I wish to convey that it is a parallel morphism.
Our setup from the question is this. We've constructed the coequalizer $(C,eq^*)$ of $f_1,f_2$, and then the equalizer $(E,eq)$ of $eq^*\circ \pi_1$ and $eq^*\circ \pi_2$. $$ \require{AMScd} \begin{CD} E @>eq>> A\times A @>eq^*\circ\pi_1,\ eq^*\circ \pi_2>> C \\ @AAA @VV\pi_1,\pi_2V @| \\ X @>>f_1,f_2> A @>>eq^*> C \end{CD} $$ The map $X\to E$ comes from the universal property of the equalizer applied to the map $(f_1,f_2) : X\to A\times A$, which unfortunately I can't include in the diagram as it goes diagonally. Anyway, this is because we have $$eq^*\pi_1(f_1,f_2) = eq^*f_1=eq^*f_2 = eq^*\pi_2(f_1,f_2).$$ Note that as claimed, the parallel pair $f_1,f_2$ is recovered as the composite $$X\to E \xrightarrow{eq} A\times A \xrightarrow{\pi_1,\pi_2} A.$$
Now suppose we had another equivalence relation, $(E',p_1,p_2)$, with $p_1,p_2: E'\to A$ and a map $F:X\to E'$ such that $p_1 \circ F = f_1$ and $p_2\circ F = f_2$.
We now need to construct a map $E\to E'$. This is hard. constructing maps out of equalizers is hard. In fact, it's easy to prove that this map doesn't exist unless we assume that $E'$ is an equivalence relation by taking a small example in sets, so we're going to need to make use of this fact somehow.
Let's use the Yoneda lemma. View $y_{E'}$ as a representable subpresheaf of $y_{A\times A}$ such that $\newcommand\Hom{\operatorname{Hom}}\Hom(Y,E')\hookrightarrow \Hom(Y,A)^2$ is an equivalence relation for all objects $Y$, where $y$ is the Yoneda embedding.
Then to produce a map $E\to E'$, it suffices to produce a natural transformation $y_{E}\to y_{E'}$, but since both are equivalence relations on $A$, it suffices to show that if $g,h:Y\to A$ are related via $E$, then they are related via $E'$ for all $g,h$.
First let's work out the equivalence relation defined by $E$ on $\Hom(Y,A)$. Let $g,h : Y\to A$. Then $g$ and $h$ are related by $E$ if and only if $(g,h) : Y\to A\times A$ has a lift to $E$. Since $E$ is the equalizer, this is true if and only if $eq^* g = eq^*h$. This should be the smallest equivalence relation generated by $f_1\circ \alpha \sim f_2\circ \alpha$, for $\alpha : Y\to X$ such that the quotient presheaf is representable, by definition of the coequalizer. (Note we need to check that the smallest equivalence relation whose quotient is representable is a well defined concept, which might require taking more general limits/colimits than we've allowed for (because we might need an intersection over all equivalence relations with representable quotients)).
Now $E'$ certainly relates $f_1\circ \alpha$ and $f_2\circ \alpha$, since $f_1$ and $f_2$ factor through $E'$. In fact, $F\circ \alpha : Y\to E'$ is a lift of $(f_1\alpha, f_2\alpha) : Y\to A\times A$. Thus, as long as the quotient presheaf is representable, we must have that for all $Y$, $y_{E'}(Y)\supseteq y_E(Y)$. (This is not obvious though). We would expect that the representing object should be the coequalizer of $p_1$ and $p_2$, but just as morphisms out of an equalizer are hard, morphisms into a coequalizer are hard, so I'm not sure how to confirm that in general. You might need additional assumptions on the category to complete the proof. Or perhaps I'm missing something.
Final note
There may be a better strategy than this, but you'll note that given this strategy, the coequalizers turn out to be unnecessary. Instead, we work in the presheaf category from the start, and take $E$ to be the smallest representable equivalence relation containing $f_1\circ \alpha \sim f_2\circ \alpha$.
The Yoneda lemma then forces $E$ to factor $f_1,f_2$, and we immediately have that if $E'$ is any other equivalence relation where $f_1,f_2$ factors through $E'$, then Yoneda gives a unique map $E\to E'$, as required.
The trick is showing that there is a smallest representable equivalence relation. For this we would need the existence of arbitrary products in the slice category $C/(A\times A)$. Then take all representable equivalence relations $E\to A\times A$ containing the desired generators, and the product in the slice category, $\prod_E (E\to A\times A)$ represents a presheaf that is the intersection of all of the equivalence relations we started with.
In other words, it suffices to assume that $C/(A\times A)$ has all finite products to produce a finest congruence for a pair $f_1,f_2 : X\to A$.