This sort of problem was what got me started down the slippery (i.e. REALLY expensive) digital SLR slope... but the ride has been fun 
For this sort of shot I put the ISO on 800 or 1600 or so, and use a fast lens such as the 85 f/1.8 or 135 f/2L, depending on how far you are away. The 85 f/1.8 is an excellent lens for the money. I use noise ninja to reduce noise from the image in post-processing.
f/1.8 is basically 2 stops faster than 3.5, so that moves your shutterspeed from 1/10 to 1/40. If you set the ISO to 1600, another 2 stops, you get a shutterspeed of 1/160. If you have steady hands then you could stick with ISO 800, f/1.8, 1/80.
A digital rebel + 85/1.8 is a great combination, but it's hard to stop!
Malcolm