As an example, gcc includes code generators that try a few random things in order to optimize code. So two builds, on the same system, won't result in the same byte code.

Also, build stamps like time, PID, path etc.

Nix already does binary substitution. It just has the assumption baked in that builds don't do anything nondeterministic (and the Nix build sandbox removes a lot, but not all, of those opportunities; the ones remaining are things like threads, hence the slowdown).