@kromonos As @draven@quitter.no suggested, we will start from a "GNU Social Push notification plugin", which interface should be independent both from a messaging technology (e.g. GCM), from AndStatus and from the plugin itself. 
I don't think that this plugin will be convenient for a released version (as usually push notifications are in the same apk as a notified application), but this surely may be used during testing/search for better solutions.

1. Notification intent (which AndStatus or other app will catch) should contain GNU social domain name, not the plugin's.
2. Notification should include this data:
2.1. Webfinger ID (e.g. andstatus@loadaverage.org) of the account to be notified.
2.2. Timeline type, which has new data ("home", "mentions" for the start...)

@kromonos Which part of the development you could take part in? The minimum is creating a server side code and making it available for testing at one of GNU Social instances?!
I will do at least AndStatus side.

Maybe somebody else would volunteer to create this "GNU Social Push notification plugin" for Android?!