Could an object of sufficient mass deflect Mars so that it ends up
stably orbiting an Earth-Mars-Moon barycenter?
A sufficiently massive object could alter the orbit of Mars to a near collision course with Earth. But some other mechanism would have to then bleed off velocity from Mars in an Earth centered coordinate frame in order for Earth to capture Mars in an orbit. Without that second mechanism, Mars would just pass closely and then zip back out again into another Solar orbit.
The Hill Sphere of the Earth is about 1.5 million km. The closest pass between Mars and the Earth is about 55 million km. So there could be no single object perturbing the orbit of Mars in such a way that it could end up being a satellite of Earth.
What if the Moon got kicked out in such a scenario?
Mars is almost 10 times as massive as the Moon. So, I don't believe any Mars/Moon flyby would be sufficient to bleed off enough velocity from Mars to allow Earth to capture Mars as a satellite. I don't believe even a collision between the Moon and Mars would provide a sufficient exchange of momentum to capture the resulting body(s).
Could an Earth-Mars barycenter exist stably and what distance would
they orbit each other if so?
Yes, an Earth-Mars binary planet system could exist stably. Pluto and Charon have a similar mass ratio as Earth and Mars. The orbital distance would need to be less than 1/3 or so of Earth's Hill Sphere distance, so anything less than 500,000 km would probably work. A smaller orbital distance would be more stable for a longer period of time (as long as they weren't so close as to collide).