What are the practical implications of this? Could cargo call GCC? Or would it be like gcj and allow compiled rust libraries & binaries to be distributed? (at least in theory, gcj didn't work out well)

There is also a project for rustc to use GCC instead of LLVM for codegen.

https://github.com/rust-lang/rustc_codegen_gcc