@maha: Check out this book:http://www.amazon.com/Head-First-Java-K ... 0596009208
I haven't checked it out personally, but I understand it's well regarded easy to digest introduction to Java. For the more hardcore coverage Thinking in Java by Bruce Eckel is nice and I believe is also available online for free. I first experienced Eckel's thorough coverage with Thinking in C++ back in the day. The Eckel book will be intense, but if you get through it you'll have a rather deep knowledge of Java.
Also another good one in the Head First series:http://www.amazon.com/First-Design-Patt ... 596007124/
If you start working with the Java2D API with J2SE desktop Java you'll find it's quite similar to the Android 2D API. Of course the API is different, but the concepts are essentially the same. If you have and Android device it's certainly fine to jump right to working with it. Consider using a device as soon as possible as the Android emulator is not the best for game dev. While the emulator works ok for the Android 2D API it will not work well for OpenGL ES dev, so get used to developing on a real device.
For Android dev I've never picked up a book, so offhand I don't have a good one to recommend that is game dev focused... Of course as mentioned I'll be writing a thorough set of tutorials soon.. Do drop me a quick email at the contact address on the web page though so I remember to send you a note when the tutorials publicly launch.
I definitely recommend to get a handle on some simple 2D applications, but another route is to use premade engines that assist in game dev. The forum owner here has created one called AndEngine. It's more of a black box engine where the internal OpenGL ES implementation is hidden and it provides an easier to use API for game creation. Another one is Rokon2D. Of course I'll be getting my platform out which has game dev features and a whole lot more soon.
I think it's fair to assume starting with Java and OO dev is gentle enough especially considering most universities teach Java out of the gate as the core introductory language for over a decade. I actually got through the uni system with C/C++ just before the switch. It is useful to know about especially since it's a little closer to the hardware so to speak compared to Java.