Using both a stepper motor and a DC motor with Arduino motor shield R3 We are trying to reprogram a remote control car with an Arduino Uno. This car runs the power with a DC motor, and it controls steering using a stepper motor.

We have the Motor Shield R3 attached to the Arduino, but it has just now occurred to us that we can't support both motors with the motor shield (as the motor shield only allows for two DC motors or one stepper motor). Is there a way to somehow work around this? Or is it possible that we would need to replace the stepper motor with DC?
You are right: Motor Shield R3 can drive two DC motors or one step motor. So, there are 2 (maybe  3) solutions:
1. Have another shield - now you can drive 2 step motors, or one DC motor(using 'half' of shield, and one step motor using another whole shield.
2. Replace your step motors with DC motor. This option can be more complicated, as no precise position control will be possible when you try to use DC motor for steering. (DC motor are hard to select and hold position, when stepper motors are quite easy to 'go to certain position' AND 'hold'). There is also good mechanical skill needed to remove/place it precisely.

optional option 3. Instead of Motor Shield R3 you can try to use cheap Easy Driver to drive your step motor.