If browser history, cookies etc are deleted, will he get push notifications?

Generally yes, as long as notification subscriptions are allowed. But some of the features which are based on subscriber id, may not work.