Admittedly, the latter strategy is a bit frustrating and counterintuitive on 16.04. When you install Docker it will start automatically and hang because it can't find the AUFS driver and Device Mapper isn't set up. The solution is to either 1. modify policy-rc.d to prevent services from automatically starting or 2. set up Device Mapper (install dmsetup and run `dmsetup mknodes`) before installing Docker and changing the storage driver. Unfortunately, these workarounds are not particularly well-documented.
I would be interested to see how Docker 1.12 or 1.13 with a modern kernel and OverlayFS would be able to handle your described workload.