Why does pushing a magnet inside a solenoid produce current? If you push a bar magnet inside a solenoid, a current is produced. But why is that? I mean, the wire is being moved along the magnetic field, so taking the cross product:
$\vec{F} = I\vec{V}\times\vec{B} = I|\vec{V}||\vec{B}|\sin\theta\hat{n}$
Here, the angle between the velocity of the charge in the wires and the magnetic field is essentially zero. So there is no force on the charges in the wire and hence no current. But that does not correspond to reality. Why? 

 A: The main problem with your approach is that you're not taking into account the relative velocity between the electrons and the magnet.
Instead of looking at the wire as stationary and the magnet as moving, choose to view the problem from the perspective of a stationary magnet with the wire moving past it. Then the velocity of the electron is not parallel with the magnetic field (the electron is stationary in the wire, but the wire is moving). In this way a non-zero force is produced.
To return the question to your scenario, with the coil stationary and the magnet moving, we have to perform a Lorentz transformation (a change in coordinates that occurs when we switch velocities, used in special relativity). Under such a transformation, a moving magnetic field becomes a stationary magnetic field plus an electric field. For more info you can read here.
In this case the magnetic field doesn't change direction, but an electric field is produced and it is this field that causes the electrons to move.
A full understanding of the dynamics of electric and magnetic fields can't work without including special relativity - this is why, usually, the question of current induction is explained in terms of Faraday's Law, which is yet another perspective on the scenario.
