Now what about caching? Why not label these pages as Cache-Control: private?

The AvantGo sync server already caches different versions of your web page depending on the screen size, operating system, and bit depth of the mobile device that is loading your page. So if you are only customizing content based on these settings, you can go ahead and cache them normally; there is no need to make them private.