Is the influence of gravity instantaneous?

The first question as stated has a rather trivial answer:

"If the sun magically disappeared, instantly, along with all its influences, how long would it take its gravity to stop having an effect on us?"

Since the Sun's gravity is among its influences, it would instantly stop having an effect on us. That's just part of the magical situation, and doesn't even involve any physics. A bit more interesting is the question without the bolded part.

In general relativity, changes in the gravitational field propagate at the speed of light. Thus, one might expect that the magical and instant disappearance of the Sun would not affect earth for about eight minutes, since that's how long light from the Sun takes to reach Earth.

However, this is mistaken because the instant disappearance of the Sun itself violates general relativity, as the Einstein field equation enforces a kind of local conservation law on the stress-energy tensor analogous to the non-divergence of the magnetic field in the electromagnetism: in any small neighborhood of spacetime, there are no local sources or sinks of stress-energy; it must come from somewhere and go somewhere. Since the magical instant disappearance of the Sun violates general relativity, it does not make sense to use that theory to predict what happens in such a situation.

Thus, the Sun's gravity instantly ceasing any effect on the Earth is just as consistent with general relativity as having any sort of time-delay. Or to be precise, it's no more inconsistent.

My big question, now, is: "How do we know it's instant?"

It's not instant, but it can appear that way.

We can't possibly move an object large enough to have a noticeable gravitational influence fast enough to measure if it creates (or doesn't create) a doppler-like phenomenon.

We don't have to: solar system dynamics are quite fast enough. An simple calculation due to Laplace in the early nineteenth century concluded that if gravity aberrated, Earth's orbit would crash into the Sun on the time-scale of about four centuries. Thus gravity does not aberrate appreciably--more careful analyses concluded that in the Newtonian framework, the speed of gravity must be more than $2times10^{10}$ the speed of light to be consistent with the observed lack of aberration.

This may seem quite a bit puzzling with how it fits with general relativity's claim that changes in the gravitational field propagate at the speed of light, but it's actually not that peculiar. As an analogy, the electric field of a uniformly moving electric charge is directed toward the instantaneous position of the charge--not where the charge used to be, as one might expect from a speed of light delay. This doesn't mean that electromagnetism propagates instantaneously--if you wiggle the charge, that information will be limited by $c$, as the electromagnetic field changes in response to your action. Instead, it's just something that's true for uniformly moving charges: the electric field "anticipates" where the change will be if no influence acts on it. If the charge velocity changes slowly enough, it will look like electromagnetism is instantaneous, even though it really isn't.

Gravity does this even better: the gravitational field of a uniformly accelerating mass is toward its current position. Thus, gravity "anticipates" where the mass will be based on not just current velocity, but also acceleration. Thus, if conditions are such that the acceleration of gravitating bodies changes slowly (as is the case in the solar system), gravity will look instantaneous. But this is only approximately true if the acceleration changes slowly--it's just a very good approximation under the conditions of the solar system. After all, Newtonian gravity works well.

A detailed analysis of this can be found in Steve Carlip's Aberration and the Speed of Gravity, Phys.Lett.A 267:81-87 (2000) [arXiV:gr-qc/9909087].

If he was wrong, how do we know it's not?

We have a lot of evidence for general relativity, but the best current evidence that gravitational radiation behaves as GTR says it does is Hulse-Taylor binary. However, there is no direct observation of gravitational radiation yet. The connection between the degree of apparent cancellation of velocity-dependent effects in both electromagnetism and gravity, including its connection with the dipole nature of EM radiation and quadrupole nature of gravitational radiation, can also be found in Carlip's paper.