Is the fingerprint thing even a problem? Is there an Android profile identifier that is visible to apps? If something like that already exists, the fingerprint from the wallpaper would not reveal any more information. I'm not an Android developer, so this question should be answered by someone other than me.
The basic color idea seems to be a good fix. I think about it like letterboxing in the Tor Browser. It is still a fingerprint but you fall into a bigger set of users. If you allow me to finish your thought, I would assume that most basic color users would use the first one so that one would be then the best choice in terms of anonymity.