It is a hard problem.

Look at the monumental effort Debian went through (or hell maybe they are also still working on it) http://wiki.debian.org/ReproducibleBuilds

Few things which makes achieving reproducible/deterministic builds hard are - timestamps of generated/compiled files, continuously updating versions of build tools(+support libraries), output binary difference compiled across different OS.

We can use docker based build system for this, but it would require very carefully configured Dockerfile to keep the build tools+libraries on specific version. And if we do a pre-built Docker Image, then the Reproducibility of that Docker Image has to be proven first. It is indeed a difficult task, but not an impossible one. With F-Droid providing a sound framework for reproducible build generation, I believe we would have majority of large Android Apps reproducible in next few years.