Newtonian gravitation is just the statement that the gravitational force between two objects obeys an inverse-square distance law, is proportional to the masses and is directed along the line that joins them. As such, it implies that the interaction between the objects is transmitted instantaneously and it must be inconsistent with special relativity (SR).
If say the Sun suddenly started moving away from the Earth at a speed very close to the speed of light, SR tells you that the Earth must still move as if the Sun were in its old position until about 8 minutes after it started moving. In contrast, Newtonian gravitation would predict an instantaneous deviation of Earth from its old orbit.
What you have discovered in your reasoning is that indeed, Coulomb's Law is NOT relativistically invariant either. But Maxwell electromagnetism is not Coulomb's Law.
As a matter of fact, Coulomb's Law is deduced from Maxwell equations as a particular case. The assumptions are those of electrostatics, namely that the magnetic field is zero and that the electric field is constant in time. These assumptions lead to the Coulomb field but they are NOT consistent with SR in the sense that they can not be valid in every reference frame since if the electric field is constant in a reference frame, then there exists another frame in which it will be varying and the magnetic field will be differnent from zero. For more you can start reading this. Maxwell's electromagnetism IS consistent with SR since the full Maxwell's equations apply in all reference frames, no matter whether the particle is moving or not.
General Relativity is the analogous for gravity of Maxwell's electromagnetism and, as it has already been said, it leads to equations for the gravitational field (the metric) analogous to those of Maxwell. Thus, it is not strange that something that resembles gravitational magnetism should appear.
Let me try and expand a bit on Ben's answer.
Starting with special relativity, the key thing to understand is that all the weird stuff, and indeed the Lorentz transformations, is derived from a property called the metric. If you have two points in spacetime separated by ($\mathrm dt,~\mathrm dx,~\mathrm dy,~\mathrm dz$) then the metric tells us how to calculate the interval between them. For SR this is:
$$ \mathrm ds^2 = -\mathrm dt^2 + \mathrm dx^2 +\mathrm dy^2 +\mathrm dz^2 $$
The interval $\mathrm ds$ is referred to as the line element and is an invariant, i.e., every observer no matter how fast they are moving, will calculate the same value for $\mathrm ds$.
The equation for the line element should remind you of Pythagoras' theorem, and indeed the only difference is that the sign of $\mathrm dt^2$ is negative not positive. It's this difference in the sign that is responsible for effects like time dilation. This is the important point to take home: this metric is all you need to calculate time dilation.
Now consider general relativity, and the effect of gravity. But first let me rewrite the special relativity equation for the line element in polar co-ordinates:
$$\mathrm ds^2 = -\mathrm dt^2 +\mathrm dr^2 + r^2 (\mathrm d\theta^2 + \sin^2\theta~\mathrm d\phi^2) $$
and now I'll write the equation for the line element near a black hole, i.e. the Schwarzschild metric:
$$ \mathrm ds^2 = -\left(1-\frac{2M}{r}\right)\mathrm dt^2 + \frac{\mathrm dr^2}{\left(1-\frac{2M}{r}\right)} + r^2 (\mathrm d\theta^2 + \sin^2\theta~\mathrm d\phi^2) $$
If you compare these two equations it should be immediately obvious that they are very similar, and indeed if you let the mass of the black hole, $M$, go to zero or if you go a long way away, so $r \rightarrow \infty$, then the two equations are the same.
This means the GR metric includes everything that the SR metric predicts, but it adds to it. So there isn't a distinction between the time dilation due to just velocity and the time dilation due to gravity. The GR metric is an extension of the SR metric and includes both. However let me reinforce Ben's cautions: it generally isn't useful to try and separate the time dilation due to velocity and the time dilation due to gravity.
Best Answer
When you say "how can we derive the Lorentz transformation from General Relativity" this is really asking "how is the Minkowski metric a solution of the vacuum Einstein equation", because Special Relativity is just the geometry defined by the Minkowski metric.
If you take the Einstein equation and turn off gravity by setting $ G = 0 $, you get the vacuum Einstein equation $ G_{a b} = 0 $. The Minkowski metric is a solution of this equation, but of course there are lots of others. From your question I'd guess you're hoping that the Einstein equation will simplify in the absence of gravity, and this will make it obvious how Special Relativity emerges. Sadly this isn't the case, because even in the absence of mass, or $ G $ set to zero, gravity waves are still allowed.
I don't think there is any way to simplify the Einstein equation to make the Minkowski metric the only solution. You can require that the first derivatives of the metric vanish, but this is really getting the flat space solution by requiring that space not be curved, which is a bit of a tautology. The problem is that SR the Minkowski metric is an assumption i.e. it's where you start from. In GR the Minkowski metric is just one among many solutions so there's nothing fundamental about it.
Have a look at http://en.wikipedia.org/wiki/Einstein_tensor if you want to play around with the Einstein tensor to try and extract the Minkowksi metric.