You have to install the VC+ build tools so that
rustc can auto-detect the helper files that are part of the building process. Or you can build using Visual Studio 2013 or 2015. There are two existing Rust toolchain families provided for Windows:
msvc is the default, and as you realized, it depends on a recent Visual C++ installation.
gnu, on the other hand, depends on GNU/MinGW-w64. It can be installed and made the default toolchain using this command:
$ rustup default stable-x86_64-pc-windows-gnu