If there was a massive enough planet outside of earth's orbit to affect it, how would the earth's velocity change? I know it would be small, but would the velocity increase or decrease?
The most famous example of this lead to the discovery of Neptune. Planetary orbits were neatly worked out by Kepler and Newton, so they had a good idea of how fast planets should be moving. Uranus wasn't moving as fast as it should have, and that lead to the conclusion that there was an 8th planet.
Assuming the two planets orbit in a similar plane and don't cross, the inner planet moves faster so it's always catching up to and passing the outer planet. When it's behind the planet and catching up, it moves faster, when it's ahead, it moves slower. The effect is, as you stated, very very small but in the case of Uranus, with an orbital period of 84 years, so it spends a couple decades being accelerated by Neptune until it passes it, then it spends a similar amount of time being slowed down by it. The observed speeding up and slowing down over years was enough to lead to a calculation of the approximate location of, and shortly after, the discovery of Neptune.
The 3-body problem is complicated and the math involved is somewhat advanced, but you can do a rough approximation of acceleration and altered distance from the expected orbit using Newton's laws of gravitational acceleration g=GM/r^2 over roughly a fraction of the orbital period. It's surprisingly small, but over a couple months (for Earth) or a couple decades (for Uranus) it works out to about what you might expect. A noticeable but tiny fraction of the orbit.
Over time, these variations balance out, so the orbits remain largely unchanged over thousands, millions and even billions of years, unless the planets happen to fall into resonance. Resonance can lead to the gradual destabilizing of orbits.
Sometimes it would increase and sometimes it would decrease, depending on where the other planet was. But we do have examples already of planets affecting other planets, for example the orbit of Mercury precesses around the Sun due to the gravity of the other planets (largely Jupiter), as well as due to general relativity. The Earth's orbit is also already affected by the other planets, but even Jupiter has 1/1000 the mass of the Sun and is much farther away, so the effects are tiny.