Baidu Android Store automatically installed without permission
Found the answer.


If your device is rooted, install 'Root Browser' from Google Play
Now go in the phone directory, and browse to /data/data/com.baidu.browser.inter.
Select and delete it.
Restart phone and you will never be bothered again by Baidu browser again.


Source: Experimented myself on Android tablet.