Estimating Real-Time Vehicle Velocity from low-frequency GPS, accelerometer, gyro and magnetometer in Smartphone
How to approach this problem? Am I even correct in using Kalman? 


Yes, a Kalman filter (or a derivative) is correct.  Rotations are involved, and 3D rotations are highly nonlinear, so you'll pretty much have to use an extended Kalman or an unscented Kalman.

The basic approach is to model the vehicle motion as position, velocity, and angle driven by the IMU output, with the phone position estimate being corrected by the GPS.

You can correct the phone orientation estimate with the magnetometer, but then you need to take into account the various compass offsets.


  How to get correct deceleration? What if vehicle is cornering?


That will pretty much fall out of the Kalman solution.  As a plus, the phone's orientation with respect to the vehicle will only matter to the extent that you need to know where the vehicle is pointing, and that should be a pretty easy, fixed transform.