You are correct that this is a difficult problem. Energy methods are required to determine the contact force because kinetic energy is stored in strain ('spring') energy during the collision, when both bodies deform.
If the bodies are assumed rigid, the contact force is undefined. As you correctly conclude from $a=\frac {\mathrm{dv}}{\mathrm{dt}}$, bodies cannot decelerate instantly (ie. $t=0$). In reality, the bodies decelerate during the time (and distance) of deformation. Without deformation, $d =0= \frac {v'-v}{2}t$, and $F = \frac {\mathrm {dP}}{\mathrm {dt}}$, require $t = 0$ and $F \to \infty$. Therefore, to determine the contact force between colliding bodies, deformation must be solved.
Impact Mechanics have been studied extensively for engineering applications. Complex collision problems are solved numerically via Continuum Mechanics and Finite Element Methods, as shown below.
In practice, analytical approximations are possible with simple geometry (and conservative assumptions)- this is discussed in the following.
Think of the problem in three time steps:
1) Before contact:
Both bodies have mass ($m_{1}, m_{2}$) and velocity ($v_{1,i}, v_{2,i}$).
2) During contact:
The time interval begins at contact between bodies and ends at the instant $v_{f} = v_{1,f} = v_{2,f}$.
The final velocity is solved by Conservation of Momentum:
$$m_{1}(v_{f} - v_{1,i}) = m_{2}(v_{f} - v_{2,i}) \; \Rightarrow \; \therefore v_{f} = \frac {m_{1}v_{1,i}-m_{2}v_{2,i}}{m_{1}-m_{2}}$$
Next, apply Conservation of Energy and assume all energy is stored in strain energy (where no energy is lost to heat, sound, etc.). Strain energy is analogous to energy stored in a spring, where the effective spring constants, $k=\frac {EA}{L}$, depend on the geometry and material of the bodies.
$$\Delta E_{Kinetic} = E_{Strain}$$
$$[\frac {1}{2}m_{1}v_{1,i}^2 + \frac {1}{2}m_{2}v_{2,i}^2]_\text{i} - [\frac {1}{2}(m_{1} + m_{2})v_{f}^2]_\text{f} = \frac {1}{2}k_{1}\delta_{1}^2 + \frac {1}{2}k_{2}\delta_{2}^2$$
While it is not possible to analytically solve for the displacement of both bodies ($\delta = \delta_{1} + \delta_{2}$), engineers simplify the problem and solve for the $\delta$ they care about1; this is a conservative assumption because it predicts a higher contact force than if both bodies deformed.
$$[\frac {1}{2}m_{1}v_{1,i}^2 + \frac {1}{2}m_{2}v_{2,i}^2]_\text{i} - [\frac {1}{2}(m_{1} + m_{2})v_{f}^2]_\text{f} = \frac {1}{2}k\delta^2$$
$$\therefore \delta = \sqrt {\frac {[\frac {1}{2}m_{1}v_{1,i}^2 + \frac {1}{2}m_{2}v_{2,i}^2]_\text{i} - [\frac {1}{2}(m_{1} + m_{2})v_{f}^2]_\text{f}}{\frac {1}{2}k}}$$
Finally, the average contact force is determined from:
$$\boxed {\therefore F_{contact} = k\delta}$$
Similarly, the same result is obtained from the kinematic equations:
$$t = \frac {2\delta}{v_{f}-v_{i}} \;\Rightarrow \; a=\frac {v_{f}-v_{i}}{t} \; \Rightarrow \; \therefore F_{contact}=ma$$
3) After contact.
Elastic collisions are idealized so that all kinetic energy is conserved. Inelastic collisions describe real collisions- some kinetic energy is permanently lost to heat, sound, plastic deformation, etc. and the resulting final kinetic energies are lower (than predicted by the idealized elastic model). A coefficient of restitution ($CoR$) is applied to the Conservation of Momentum to reflect the bodys' final velocities. Note that for elastic collisions, the $CoR=1$. While inelastic collisions are more accurate, the $CoR$ is often unknown; therefore, collisions are assumed elastic to provide a reasonable estimate.
1 "Machine Design: An Integrated Approach (2nd Ed.)"- Robert L. Norton
