Consider the possibility that introducing an arbitrarily small tame asteroid could throw a planet out of the solar system. This would be a different kind of instability than those that have been so far considered. It would be of mathematical interest to prove that a system consisting of a sun and three planets could be disrupted by a single arbitrarily small tame asteroid.
Notes:
1. Another way would use multiple asteroids from the Kuiper belt or even the Oort cloud. Maybe no Jupiter or Venus, and each asteroid makes a single pass and is kicked out of the solar system. Many can be en route at once. I suspect several times the mass of Mars will be required. specifically in the ratio of the escape velocity from a solar orbit at Mars distance from the sun to the Mars escape velocity. A single Jupiter pass may improve the numbers.
2. It looks like a lot can be worked out by considering single collisions. For example, suppose an asteroid from far out has an elastic collision with Mars. It will take energy and angular momentum from Mars. I suppose that if it were to collide again with Mars it would tend to give back what it took. How does this modify if we have an intermediate collision with Jupiter or Venus? In the end we need both, but let's see what happens with one.
3. It may be a lot easier to move Mars than the above considerations suggest. The solar system is a lot more chaotic, even in the short term than was thought 10 years ago. I found [PC05] very informative about exotic orbits as applied to spacecraft and as observed and calculated for the short period comet Oterma. Whether this would help move Mars would require difficult mathematics and computations, at least by present standards. Our descendants my find the matter obvious.
Tom Costello commented usefully on an early version of this article. I have learned from [DGK01], and its ideas have triggered further thinking, as has discussion with Don Korycansky and Greg McLaughlin. R. William Gosper used Macsyma to solve the quartic equations.