I can confirm that this is now working for Verizon GS5s now on stock ROM, unrooted. However, my voice controls are not working and I'm looking to see what I may need to do before I consider a factory reset.
You will need Google Play Services (GPS) 7.5.71 and the most recent version of Android Auto for this.
To get the latest GPS version. Update your Google Maps, Google App, GMail, etc. to the latest version.
Then go into Application Settings and find Google Play Services under "ALL" apps.
Clear that application's data, cache, and uninstall all updates, reverting it to stock state.
Immediately you should get a notification that an app requires an updated version of Google Play Services. Click this notification and follow it through to the Play Store.
Update Google Play Services to 7.5.71.
Once this is done, make sure your car is in parking brake on state (or an "emulated" park state, i.e. bypassed), connect your phone to the car stereo and begin the Android Auto setup process.
This won't work if you sideload (from APK Mirror) the Google Play Services, I've found. However, the "uninstall updates" method works to force you into the newest Google Play Services version (I was unaware that this was the way to get GPS out of the Play Store).