Arduino Vehicle Remote Start
It would work if you connect the relay exactly parallel to the starter switch poles. Make sure you do not bypass other circuitry, which could contain some safety mechanism. Also I would recommend doing this with a experienced/professional electrician, for your own safety.

Regarding the follow-up question, since they are connected in parallel, it would not make a difference if both the relay and the switch are activated at the same time. The starter will run when the relay OR the switch is activated.