Think Java: How to Think Like a Computer Scientist is intended as an “initial exposure to programming constructs and techniques” (p. xiii) for computer science students with no or very limited programming experience.
Published through Green Tea Press under a free license the book can also be purchased through O’Reilly Media as a hard copy.
I don’t know whether I would choose this book for teaching Java – should I ever be put in the position of teaching it – but I would definitely consider it.