Yes, you can update your Widgets in reaction to a push notification.
Assuming that your push notification kicks off a service or something, you might have a method like so:
private void updateWidgets() {
AppWidgetManager appWidgetManager = AppWidgetManager.getInstance(this);
// Get a list of the widgets that need updating
int[] widgetIds = appWidgetManager.getAppWidgetIds(
new ComponentName(this, MyWidgetProvider.class)
);
RemoteViews updatedViews = new RemoteViews(); // Actually get the updated views
appWidgetManager.updateAppWidget(widgetIds, updatedViews);
}