I've thought about this for a long time. Nice to see it getting attention.
this is why I don't really appreciate Graphene's sandboxed google play services as much as I appreciate MicroG. MicroG allows you to control which GPS-compatible apps get registered to your random ID on google's servers.
It's also worth studying your individual apps and how exactly they handle google push notifications. I know that there are various configurations, some which allow Google to see the content of the notification and some which done. of course, regardless of that, metadata such as who it gets delivered to and when, is still there.