Is it possible to use two encoders with Arduino Uno?
It is very possible. use a separate interrupt pin for Phase A of both motors, then read phase B from a non interrupt pin in the interrupt handler.
http://www.spiked3.com/?p=5501