Those old phones didn't run Java for anything that mattered. The OS itself and all the core apps would be native code. Java - J2ME, usually - was for third-party apps, and it was slow enough that you didn't really see anything "serious" there (e.g. I haven't ever seen a full-fledged J2ME web browser - the most we got was Opera Mini, which did all the layout computations server-side).

Same thing for early PDAs like Symbian and WinCE devices - all software running on those would be native. Well, WinCE got .NET at some point, and it was usable, but that one is fully JIT-compiled.