Is an omnidirectional antenna a must for a cell phone?
This is partially not entirely true anymore. With increasing bandwidth requirements and as we are getting really close to the theoretical limit of omnidirectional picojoules/bit, in order to increase bandwidth in cell phones it will definitely be necessary to go back to directional antennas again. The way this is solved in the next generation of radios (and I believe the current generation of Qualcomm 2x2 LTE radios) is that they employ a phased array antenna using the 2 send and receive antennas. g-sensor data is used to 'point' the phased array in the right direction in the short term, and receive antenna tuning is used to lock the phased array in the long term. As we go towards 2020, phased arrays and possibly eventually focused array will become commonplace and necessary in handsets to achieve next-generation data rates.

addendum: this method of using multiple antennas as a phased array is called beamforming.