OOP is all about concepts and not about languages !
The problem with Java is that its Class Library (API) is itself a very sophisticated OO architecture , already using/implementing a lot of advanced OO concepts (like patterns) and system techniques (like threading , delayed calls in Swing)
I began OO programming in 89 with Borland Pascal for Objects. And i found the OO approach very well explained in the manuals .
Using the classical 'figure' example to explain virtuality and inheritance.
I saw a lot of "young" java programmers falling into the trap of using the class library without knowing the concepts they were manipulating just because Java had already implemented these concepts and made them easy to "call".
But calling already made objects is exactly what's done in Visual Basic which is all but an object oriented language (not speaking of VB.Net which is no more VB)
"Hello world" has simply no architecture. It is not an example to take for OO teaching !
The main interest in OOP is creating objects suiting an application architecture. For creating these objects, you can use other objects of course.
You can't teach Java before teaching OOP . But you can use Java as an OOP teaching language by using only the java.lang package and taking the approach of "problem solving".
I explain : ask the students how they would do something and tell them the benefits of doing it in an object way. By taking this approach, you could focus on each OOP concept , by refining the solution provided incrementally.