Xcode 8.0 Automatically Manage Signing behaviour
With the release of Xcode 8, Apple introduced a new way of managing the signing configuration. Now you have two options Manual and Automatic.
This new Automatic Signing doesn't work the same way as it did in previous Xcode versions. Before, when you set Automatic provisioning profiles, Xcode was using the first provisioning profile and certificate in your computer that matches the entitlements and bundle identifier that you were trying to use.
In Xcode 8, Automatic Signing is going to manage profiles, entitlements and certificates for you, but only for Development. If you select automatic, you are forced to use Development signing and Xcode-created provisioning profiles.
On the WWDC 2016 (Session 401 - What's new in Xcode app signing) they explain this new signing method and describe some 'Best Practices'. When you are building for distribution and using Automatic Signing or Manual you should Archive for Development and then export (from the organizer or the command line tools xcodebuild -exportArchive) as Distribution. The organizer will re-sign your app for Distribution even if it was archived for Development.
The other issue that you describe, "Missing Push Notification Entitlement" is because Xcode 8 has changed the way it applies entitlements. With previous versions of Xcode, you didn't have to explicitly add the APS Environment entitlement, it was enough if your provisioning profile had that entitlement. Make sure that you have the Push Notification capability enabled in the Capabilities tab, and check that there are no errors there.
(Edit: this new behavior is intentional and described in the Xcode 8 release notes: https://developer.apple.com/library/content/releasenotes/DeveloperTools/RN-Xcode/Introduction.html#//apple_ref/doc/uid/TP40001051-CH1-DontLinkElementID_44)
Xcode 8 does not automatically copy the aps-environment entitlement from provisioning profiles at build time. This behavior is intentional. To use this entitlement, either enable Push Notifications in the project editor’s Capabilities pane, or manually add the entitlement to your entitlements file. (28076333)