How much is airspeed reduced on an A10-Warthog when firing its cannon?
What acceleration is being applied to the aircraft (In m/s or kt/s)?


From XKCD we know that the gun


  produces almost five tons of recoil force


that is about 50000 newtons (round numbers for simplicity, they won't overly affect the results)

The acceleration is force divided by mass, and the A-10 has an empty mass of 11000 kg, and a MTOW of 23000 kg.

This gives an acceleration between $4.545\ \mathrm{m/s^2}$ and $2.174\ \mathrm{m/s^2}$.

The Wikipedia page about the GAU-8 mentions that 


  While this recoil force is significant, in practice a cannon fire burst slows the aircraft only a few miles per hour in level flight.


and gives as a reference a book that I do not own, so I cannot verify.




  If there was infinite ammo and nothing like gun overheat, how long would it take to slow the plane down to stall speed, if initial speed was a usual A-10 speed.


With the additional assumption of thrust balancing only the aerodynamic drag, we can say the following: cruise speed is $155.6\ \mathrm{m/s}$, and stall speed is $61.11\ \mathrm{m/s}$ (see Wikipedia link above), so this means that it would take between ~34 and ~71 seconds to completely stop the aircraft; or between ~20 and ~43 seconds to stall it.



If instead we want to be more realistic, we have to assume that we have infinite fuel, that ammo and fuel do not factor in the weight computation, and that the yawing/pitching moments do not overcome actuator authority.

With all that in mind, we should start from firing the gun at strafe speed, not at cruise speed, since we want to hit a specific target on the ground, so we want to move as slowly as possible, to have the highest chances of hitting it. This means that our starting velocity would be above stall speed but not significantly, leading to a smaller margin of continuous fire before stalling, unless the throttle is opened (if possible) to counteract the extra "drag".

If we ignore the discussion about strafing and hitting the target, and we fire from cruise speed (and this is what is meant by "usual speed"), it is possible that stall is not achieved, since at lower speeds you will have more excess thrust (but we are still assuming that the firing only produces "drag" or a negligible amount of yawing/pitching moments). This means that we could settle at a lower speed, but the determination of the exact speed requires the knowledge of the exact drag and thrust characteristics of the aircraft, in addition to it being a function of the initial speed, see Koyovis' answer for some basic numbers.