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.
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.
Best Answer
I would say, that your two first statements are not wrong, i.e. you can defend them in a discussion if you explain what you mean by extension and special case.
Your conclusion, as you suspected anyway, is wrong however. Special relativity and Newtons law of gravitation are not the same thing. In fact they deal with different aspects of a physical theory.
Special relativity is better compared to Newtons laws of motion. Both try to answer how objects move through time and space in the presence or absence of external influences like forces.
Newton's law of gravitation is a way to get one of these forces that might act on bodies.
General relativity now combines both aspects into a single theory where a mass is moving 'forceless' in a geometry 'created' by all kinds of energy.
So if one says that general relativity is an extension of special relativity it possibly means that the equations of motion of a testbody look like the equations of special relativity in the right limit. If you state that Newtons law of gravitation is a special case of general relativity, you are stretching the fact, that in the right limit the 'creation' part of general relativity looks like Newton's gravitational potential.
So to put it very short and colloquial, you are looking at different sites of an equation in these two statements.