How to provision an Android phone automatically?

Question

tl;dr: How can I write a short declarative description of the state I want my phone to be in, and then apply it to a phone?

After a factory reset or hardware change it's always a pain to get my phone back to a usable state. At the same time I don't trust any random third party service to store my settings:

• I don't have fine grained control over what they actually store. They may sell or leak that information without my knowledge or consent.
• They may be incompatible with future hardware/software, and I won't know until I try to restore.
• They may be incompatible with my configuration (try updating Android after rooting your phone, for example).
• They may at any time be shut down.
• I'll bet none of them allow me to retrieve the data in such a way that I can migrate to another service.

Setting up this sort of thing for your own PC requires very little technical skill and a little time - I've already set up a repository to provision my own desktop and laptop. However, I've no idea how to do something similar on Android. I can't see any mention of a Puppet client, and I don't know if it's possible to provision a device in any sensible way without installing a custom kernel or rooting it.