One rather quick thing you could try is employ the method home computer games used in the 80es (yep, I'm that old).
Draw the current tiled background into a bitmap +1 or +2 tiles at every direction you want to scroll into (so it's a rect which is 1 or 2 tiles bigger then the screen). Then just draw this one bitmap and scroll it until you hit it's border then at this moment redraw the bitmap. As you are no longer drawing individual tiles this should somewhat improve the fps, only problem which could arise is that the redraw of the bitmap every x tiles is too noticeable a drop in the framerate.
Apart from this this seems like the perfect case for the famoust Google IO video about Replica Island:http://www.youtube.com/watch?v=U4Bk5rmIpic
Although I have to say that from my own experience the performance improvement gained by moving to OpenGL is quite a bit less impressive then this video makes it out to be.
Using Canvas is much less of a hassle and is guaranteed to work on every device. I would recommend first trying to optimize the hell out of your game. Personally I have found that with the abysmal DalvikVM the smallest things can eat up a ton of CPU time.