Checked all drivers in device manager and uninstalled any that were not Microsoft's own like IDE, HID and network ticking the box to delete driver if available rebooting where necessary.
After three months of struggling with this I've also, finally, got it to install. In my case the driver solution was slightly different, but it fixed the problem (unless Microsoft have silently released yet another update of KB2919355 in the last week or so and that was what fixed it).
So my laptop is a Toshiba (an Ultrabook, so no install media and no DVD drive even if I had some, definitely an I've-fallen-and-can't-get-up situation), as a last resort I called their tech support and they said I should run the Toshiba Service Station app, which does exactly what Windows Update does except for some reason Toshiba feels the need to implement their own version. I wasn't expecting much, found it on the Toshiba site and ran it, after several retries it updated/reinstalled various pieces of crapware that Toshiba ship with their PCs, the only significant item I could see was an Intel Matrix Storage Driver update (which seems odd since you'd think it'd come down via Windows Update anyway).
So I unhid KB2919355 and went through the endless install process yet again... and it worked. Instead of saying "We couldn't complete the updates" as it had for the past three months and taking an hour or so to undo things, it continued on to the desktop and let me log in. The status for KB2919355 was "Pending restart" (even though the system had just restarted), so I restarted again and it reported a successful install.
After that it was just a case of the Windows Update version of Beat the Bartender, apply updates, reboot, apply updates for the updates, reboot, apply updates for the updated updates, reboot, etc, until things reached steady state. There's currently one update that won't install, but it's for Windows Journal which I never use anyway.
So if people are desperate enough for this I would echo what the OP suggested, uninstall or disable all non-MS drivers, and in particular vendor-supplied crapware, and see if that fixes it.