There's no way that the accelerators/gyrocscope would be accurate enough to remove the shake. According to google, the iphone gyroscope is accurate to within about 0.5 degrees, roughly two orders of magnitude away from being pixel accurate in a 1x zoom image.
Maybe, but it looks like a problem of unscrambling an egg. The true image has been smeared over the sensor, superimposed on itself a bit. Maybe there is a good enough solution for the problem of finding the true image, but I can't imagine it to be computationally inexpensive.
Why the requirement? The phone already has accelerometers, doesn't it?
In any case, less hake should still be easier for the phone to deal with. Those algorithms aren't flawless.