How to change Android device's default search engine?
Not currently possible. It's not locked in to Google, but determined by manufacturer and/or carrier. (For instance, there was a bit of a tempest in a teapot when a new phone was released with Bing as the search engine.)

I do not know if this is something that can be got around by rooting.