Does throwing a penny at a train stop the train? If I stand in front of a train and throw a penny at it, the penny will bounce back at me.
For the penny to reverse its direction, at some point its velocity must go to zero. This is the point it hits the train. Two objects in contact have the same velocity, so the train must come to a stop for the penny to change its direction.
I assume I'm getting some principles wrong. Is it because I assumed a perfectly rigid body, when in practice the train actually deforms ever so slightly?
 A: It looks like there's a hole in your reasoning. If I understand correctly, you're saying this:


*

*At some point, the penny's velocity must be zero.

*At some point, the penny's velocity must be equal to the train's velocity.

*Therefore, at some point, the train's velocity must be zero.


Both 1 and 2 are true (assuming that the collision is exactly head-on). But 3 does not follow, because 1 and 2 happen at different times. Specifically, 1 happens before 2 happens.
The two events both happen during the collision, so they happen within an extremely short interval of each other; but still, they happen at different times.
A: 
Two objects in contact have the same velocity

No, not always. Take two balls and make one roll faster than the other and make them collide. They do collide with different velocities!
But, in your case, if the coin hits the train and exerts a force capable of accelerating it in the opposite direction of its movement until its velocity becomes zero then yeah, the coin will stop the train.
A: If you assume rigid bodies (no deformation) then actually the coin never needs to have zero velocity since it can instantaneously change directly. In reality though, the centre of mass must pass through zero velocity (in your frame of reference). However, this does not mean that the train will stop! It will slightly decrease its speed due to change of the coins momentum, but this will be unmeasurably small.
What will happen is that the point of contact will stop (kinda, see below), and the amount of time it is stopped for (or close to) will be tiny because of how light the coin is (you can play the same game with a fly). This will leave a small dent in the front of the train, but actually most of that dent will bounce back due to the flexibility of the metal. For a coin there will likely be a remaining dent, but for a fly there will be no lasting damage to the metal and the only effect of the initial dent will have been a small sound (and a flat fly).
Now, let us look at the problem on a smaller scale. For rigid bodies we assume that matter is continuous and that touching really means touching. However, reality is different and matter is made of atoms and touching means electrostatic repulsion. This means that the train will apply force to the coin (and vice versa) when the atoms are not touching! The atoms of the train never have to actually stop! Otherwise, the same basic arguments still hold and for a sufficiently fast train, a coin will leave a dent. However, if we are talking about trains and coins on atomic levels then our model has become too complicated...
Exercise: you could try to calculate the impulse (integrated force) or even the peak force on the coin due to the metal front of the train. You will have to estimate the speed of the train, the mass of the coin, and the depth of the indent in the train front. I'm guessing even for a coin the peak force will be pretty high!
A: What does change the velocity of an object? Force of course. (Acceleration is the change of velocity). The question is how much time does it take to make that change? A long time? Infinitely small time? Momentarily? Well, it depends on the acceleration itself! If you accelerate in your car, it'd take a significant amount of time to go from $0$ to $100\ \mathrm{km/h}$.
But what about penny and train? Well if you consider the time of collision itself, you can answer your question. In real world, the front of train will slightly deform, so you are not dealing with perfect rigid body. Yes that part of train (where collision happens) stops momentarily as penny bounces off back, however other parts of train will keep their movement without caring about that part, hence deformation happens (and no, the train will not stop entirely, just contact point stops for a moment). It's completely intuitive to imagine that as the time of collision reduces, the deformation of train also decreases. Does that mean if train was a perfect rigid body it would stop entirely as collision happens? (because deformation is not possible for rigid bodies) Nope! It's because the time of collision itself for rigid bodies are "zero"! Penny and train will change their velocity instantly in that case without passing from zero velocity. 
Mathematically speaking the exerted force of a rigid body in collision is Dirac's delta function $F=A\,\delta (t)$. It's zero everywhere except at $t=0$ (time of collision) where it becomes infinite. From $F=\frac{\mathrm dp}{\mathrm dt}$ we can see that
$$\int F\,\mathrm dt=\Delta P$$
If we assume that duration of collision is anything other than zero, (i.e. there is infinite amount of force for a considerable amount of time) $\Delta P$ will become infinite which is clearly wrong. Hence neither of penny and train will stop even for a moment (like $10^{-10}\ \mathrm s$), they just can change their velocity immediately.
A: It depends. In principle it could, in any realistic situation it is not even close.
As you said, it comes down to the fundamentals. When you throw a coin at a train, the train will exert some force on the coin via electrostatic repulsion. On the atomic level this is due to the electrons in the coin getting too close to the electrons in the train and repulsing each other. This force is called the normal force and it accelerates the coin opposite to its initial velocity, it bounces back.
By Newton's third law the force acting on the coin leads to an equal and opposite force acting on the train. However, because the train is much heavier than a coin, the force that manages to measurably accelerate a coin doesn't change the trains speed by much (even measurably).
Now it should be clear that a coin will NOT stop a train unless it is an extremely slow train moving on frictionless rails. However, at some point the coin WILL have the same velocity as the train (non-zero, with respect to the ground). One can see this by considering the coin's velocity as it reflects off the train's surface. It starts having velocity opposite to the train, and ends with velocity in the same direction and slightly higher in magnitude (assuming the coin reflects elastically and doesn't just stick to the train). 
I hope this explains it :) 
A: The principle that two objects in contact have the same velocity is only true if they are in contact for a period of time.  In the simplest modeling of the situation, the coin and the train are only in contact for an instant, where an impulse is transferred to the coin to send it clattering out of the way.
The rule that two objects in contact have the same velocity stems from the fact that two objects which are in contact for a prolonged period of time have some function defining their displacement (such as "the center of box A is exactly 5cm ahead of the center of box B.")  Necessarily, such objects must have the same velocity.  The derivative of the displacement is zero, and the derivative of displacement in general is the relative velocity of the two objects.
In "the real world," the impact does indeed take time.  Very rapidly, electrostatic forces will being the relative velocities of the atoms on the edge of the penny and the front of the train to basically the same velocity.  This will propagate through the coin and the train at the speed of sound in those materials.  These wave-like propagations will eventually leave the coin with a forward velocity, and it will leave the surface of the train.
If the train was replaced with a supersonic plane, or the coin was replaced with a bullet faster than the speed of sound in the material of the train (which is faster than the speed of sound in air), then these propagations would not form nice easy wave behaviors.  Instead, there would be a shock wave and we would need to use much more complicated modeling to describe what happens... but in the end the situation will become a subsonic one, having bled the coin/bullet of its energy, and the coin will once again rebound off the train (if it doesn't shatter)
A: I think this is a great question.  I'm not 100% sure this is a complete correct answer, but I'm at least well over 50% sure.
Here are the paths of the penny (in green) and the train (in red):

First observation: The penny might never have velocity zero; at time $T$ it can jump discontinuously from a positive to a negative velocity.
Second and more important observation:  It makes no sense to talk about the "speed of the point of contact" because the point of contact exists only for  an instant.  To define the velocity at that instant, we'd need to know the point of contact's location in some interval of time around $T$, and there is no such location. 
This ignores the (very slight) deviation of the train from a straight red-line course and also ignores all the stuff about deformation of material, all of which is true but none of which (I think) is necessary, because (among other things) this picture seems to answer the question even in a theoretical case where there is no deformation.
Edited to add:  It's worth noting that the penny's worldline can't be differentiable.  If it were differentiable, it would be tangent to the train's worldline at the point of collision, which means that the penny and the train would share a well-defined velocity at that point.  Moreover, that velocity would have to be negative, because the train's velocity is always negative.  This would mean that the penny must have turned around (i.e. achieved zero velocity) before the time of impact, which requires you to believe that it saw the train coming and tried to retreat.  I hope we can agree to rule that out.
Therefore the picture above is not just one possibility; it's the only possibility (assuming rigid bodies of course).    
A: This may be easier to understand assuming that the train and the coin interact during some short and measurable time via forces, caused by elastic (spring-like) deformation of the metal surfaces involved. In other words, imagine there is a tiny short spring between the coin and the train. 
Both train and coin are subject to the same interaction force so move with acceleration. However the acceleration depends also on the mass of the object, a = F/m. As the coin is much lighter than the train, its acceleration is much greater and sufficient to change the velocity through the zero to the opposite (delta v = -at). The train is much more massive, and while the braking force is the same as for the coin, this force is not sufficient to change velocity much during the short interaction time.
A force from the real spring would go through some changing profile during the interaction, reaching the peak at its maximal compression. But this does not change the general logic of the explanation.
A: Model the train as a tiny mass (the part that the coin is going to hit) connected to a great mass (the rest of the train) by a spring (representing the elasticity of the metal that’s hit). In this model, the tiny mass will indeed equalize its velocity with that of the coin, at some point being at rest relative to the rails, before elasticity causes the coin to rebound and the spring to restore the relative positions of the masses, slowing both down ever so slightly.
Consider also that interactions propagate at finite speeds no greater than the speed of light, in this case at the speed of sound in the material of the train. For a sufficiently long train, its rear won’t even sense the collision until after the fact.
A: There is momentum conservation. Assuming the penny gets reflected, i.e. the momentum picks up a sign in the scattering process, you will have 
$$ \vec P_\mathrm{train}^\mathrm{after}=\vec P_\mathrm{train}^\mathrm{before}-2\,\vec p_\mathrm{Penny}^\mathrm{before}\;.$$
This assumes a one-dimensional motion, i.e. penny and train move along the same direction. This tells you that if the train is slow enough, or if the momentum of the penny is large enough (which is not very realistic since a the scattering won't be elastic), you can stop the train or even make it move the other way. If the momentum is not so large, then the train won't stop. 
But in general the train won't stop. You are saying that the velocity must  go to zero. This is not correct. The velocity in which frame? In the rest frame of the train its velocity is zero.
A: No need for modern physics here. Assume that the train have a velocity $\textbf{v}=v\textbf{i}$ just before the collision. The penny will collide with a small (elastic) part of the train at $t=0$; the velocity of this part relative to the train will change from $\textbf{0}$ at $t=0$ to $-v\textbf{i}$ at $t=t_c$ ($t_c$ is the duration of the collision, that is the 2 bodies will separate at $t_c$) so its velocity becomes $\textbf{0}$ relative to the earth at $t=t_c$. After $t=t_c$ the velocity of this part relative to the train quickly becomes $\textbf{0}$ again while it restitutes.
A: An elastic collision does not take place instantaneously.  Rather, the two objects are "in contact"  over a short amount of time.  By "in contact", I mean that they are each exerting a force on the other.  
In your analysis,  you have taken the view that it all happens instantaneously.  In particular, your claim that the two objects must have the same velocity during the collision, and your claim that there is an instant when the penny's velocity must be zero, are not necessarily the same instant in time, contrary to your analysis.  
An elastic collision between a penny and a train might last,  let's say, a tenth of a second.  During that tenth of a second,  the penny is decelerating to zero  (relative to you) and then accelerating towards you, until it breaks contact with the train.  The train is decelerating by an imperceptible amount relative to you.  
There is a point in time when the penny's velocity, relative to you, is zero.  There is also a point in time when the penny's velocity and the train's velocity, both relative to you, are the same.
But they are not the same points in time.  They are both somewhere within that tenth of a second, but they are not the same point in time.
A: One of the skills in being really adept at physics is learning to spot what assumptions you have made in any given line of reasoning, and then asking yourself whether those assumptions are good.
In the present case you made the following assumptions:


*

*The speed of the penny passes through zero in this physical example.

*The velocities of two objects in contact are the same.

*A given physical object such as a train has a single velocity at any given time.
Assumption 3 is incorrect, and because of this, assumption 2 is too loosely worded to be useful. A non-rigid object does not have a single velocity: different parts of the object can have different velocites, and this is what happens for the train. Almost the whole of the train keeps moving forward, but a little section of the front of the train gets squashed and momentarily has zero forward velocity before bouncing back.
If one tries to insist that extended bodies can be strictly rigid, then one enters into some other physical theory, one that does not apply to our universe. That is ok as a project in theoretical physics, but then you would have to proceed carefully in order to specify what your toy theory does and does not assume about laws of motion and things like that.
A: No. Train does not stop.
If a flying leaf hits train light if both are non elastic, at contact leaf velocity is zero but train light velocity is not zero.
