With two wheeled robot like this one, I have managed to stabilize it while keeping it stationary. This was done using a digital feedback control system by reading the position of the wheels to determine position, and the natural back electromotive force from the wheel motors was used in the feedback loop to determine velocity. It was kept stable with a PID controller, which was designed using a root locus algorithm to keep it stable and modulate the performance parameters (such as percent overshoot, settling time, etc.). I wanted to attempt to keep it stable while simultaneously propelling it forward, but I couldn't figure out how to go about designing a linear controller that could do that. Is it possible to both propel the robot forward and keep it stable using a feedback controller on the wheels, or is a gyroscope necessary?
You could use other ways of measuring orientation, such as an accelerometer, optical tracking of markers, or a depth sensor pointed at the floor.
If you managed to get it stable in a stationary configuration, I don't really see how it would be much more difficult to get it stable for a constant velocity. From a system model point of view it would effectively be the same thing bar some velocity offsets. If the transitions between velocities are not very large it should fall within the range of the natural system perturbations.
You need some sensors to detect the state of the system.
First linearize the system into a state space form, then consider what sensors you do have. Then check if it is observable. If it is observable, then you can feed the estimated states into your controller.
Currently, it sounds like you are using the wheel position and back EMF (for velocity) as direct measurements. Without checking the observability matrix, I am unsure if the system is observable.
Mathematically, the fact that you now have rotation (mostly) eliminates that parameter as a possible control parameter. Basically you'd have to redesign your algorithm to accept a large and variable angular velocity component while still using angular velocity in your feedback. The less noisy this is, the better the probable outcome simply because you're likely going to apply a differential of position to derive another control parameter. Or rather that is one way. So it does look like you need another control input, but it need not be an accelerometer. You could do a horizon, fixed marker location or even tilt sensors.