From a Microsoft Answers post:
The default search engine is indeed set by the provider. At the moment, there is no way for the end-user to override this default. Many have asked for this feature, and I really hope we get it in a future update as the current behavior is anything but user-friendly.
So there doesn't seem to be an official way at the ...
Considering Bing is not just used for mere searching, but also integrates with the marketplace, and have support for places, vision, music and voice-search, replacing it with Google would require a large number of Google Services, and not just the search-engine.
It is not possible to change when the Bing wallpaper runs a wallpaper update on your phone but you can use other apps such as Locksider, PhotoStream and My 500px to achieve what you are looking for.
Among the above apps, PhotoStream is free and the other two are not (you can try them for free).
It may be possible that the background task that updates the lock screen has been turned off. There is an article at WPCentral that details how to make sure background tasks are active for the apps you want.