I suspect not, because moving forward (or backwards for that matter) is an important part, but I would like to confirm.
UPDATE: Clearly it's possible http://www.youtube.com/watch?v=NuJvH1W7s1Y Can someone explain why?
When you begin to fall to one side, you are effectively leaning into a turn. Because the contact patch of the front wheel trails slightly behind the center of the steer tube, leaning over causes the steer tube to turn at a more acute angle than the radius of the turn given sole by the lean amount. Because the handle bars are turned into a tight[er] turn, the bike begins to turn under the center of mass of the bike and rider. This animation on from Wikipedia's Bicycle and Motorcycle dynamics article shows this process.
Basically, bicycles are self-righting because they are always turning (or being turned) to stay under the rider's center of mass. At slow speeds, the weaving is noticeable as in the animation. At higher speeds the weaving will become so fast and small that it becomes imperceptible by the rider. In the presence of additional forces on the front wheel (such as a rough surface or wind), additional rider inputs are often needed to counteract these forces and keep the front wheel on the angle it needs to be to keep the bike under the rider.
This article by Dr. Hugh Hunt (University of Cambridge Department of Engineering) does the math on the gyroscopic forces when riding a bicycle and finds that at 12mph they are only strong enough to counter about 2mm of lean and not a significant contribution to stability. Additionally, it catalogs an experimental test where a second counter-rotating wheel is used to cancel the gyroscopic forces -- and the bicycle suffers no noticeable decrease in stability:
The main reason is not balancing, but a physical phenomenon called gyroscopic effect. In principle this is the fact that a rotating body tries to keep the axis of its rotation fixed in space and also the reason why a spinner stays upright as long as it spins. The gyroscopic effect makes rotating things self-balancing an works better the faster the rotation is -- hence it is much harder to not fall down as you cycle very slow (which means the wheel rotate only slowly) compared to higher speeds.
If you had to balance the whole thing just by actively balancing, you wouldn't stay up for long. Compare trial cyclists: they invest hours of practice into balancing on their bike while standing and even then have to work a lot on their bike with rolling or hopping slightly back and forth or aside to keep their center of gravity balanced over their bike. You could not do this on a treadmill if you neglected the gyroscopic effect.
So what is now happening on a treadmill that keeps you up? As you tend to tilt to one side, the gyroscopic effect jumps in with some rather unintuitive behavior: if you apply a force perpendicular to the rotation axis (which is what you do when you try to tilt the bike) the gyro reacts on this with another force that is perpendicular to both the rotation axis and the initial force. So if you consider the rotation axis to be parallel to the ground (and perpendicular to the wheel plane) and the tilting force perpendicular to the ground, the resulting force will be perpendicular to both of them, i.e. lies in the plane of the wheel and parallel to the ground. This force will turn the wheel out of its initial direction like you do when you turn the handle bar to steer.
But (and here comes the magic) this will again result in another force that is again perpendicular to the ground and therefore a tilting force but in the opposite direction as the initial tilting force and therefore it will make the bike get more upright. This will again induce a "steering" force and as long as the tilting is rather small it goes back and forth resulting in some oscillation where the bike tilts slightly right and left but always stays nearly upright.
Important security notice: As already said it's quite unintuitive. Even if one in theory knows how it works, one should not try to forcefully probe some of the implications. I know of a physics professor that had a nice crash on thinking he knew how it works.