The 'java' program doesn't search for ld-linux. ld-linux is a loader (hence the name) and runs before the executable, in this case java, even starts. That's why it's your shell reporting that java couldn't be started, not java reporting that it had trouble initializing something. There are ways to change where ld-linux searches for other shared libraries needed by an executable but they can't work for ld-linux itself, because (as far as we can observe) the universe is causal and time flows in one direction.
I haven't tried it, but the accepted answer to https://unix.stackexchange.com/questions/17428/moved-bin-and-other-folders-how-to-get-them-back (where someone accidentally moved their /lib including /lib/ld-linux* to the wrong place) says you can explicitly run a specified ld-linux (presumably any working one) and have it run your executable, here java (presumably with appropriate arguments).
But I wonder why you think you need to change ld-linux, since it's actually gone once the program runs. If you just want to change what gets loaded, LD_LIBRARY_PATH and maybe LD_PRELOAD can do that, without any change to ld-linux.