Why doesn't Time Machine do scheduled backups after my Yosemite -> El Capitan upgrade?

I'm having a very similar problem after upgrading to El Capitan, except that I can not repair the disk, my attempt always gives me a repair failed error. I don't have an answer, but I think I can verify that the issue probably isn't related to any third-party extensions as I'm operating without. So at least I may be able to help rule out those as a source of the problem.

Apple's engineers will need you to run tmdiagnose to get at the root cause. In the mean time, you could gather those logs and also try to push at the status:

tmutil latestbackup
tmutil listbackups
tmutil startbackup --rotation --auto
sleep 15; tmutil status

My guess is you have a spotlight issue or an issue mounting the drive that's failing as opposed to launchd falling down. You could make a cron entry, but I'd use a tool like Lingon to make a custom launchd job to call the startbackup command from above to at least have some periodic coverage while you gather enough information to figure out why your jobs are not starting.

Also, I would try adding a second backup destination to see if that one works more reliably - multiple backup destinations should fire sequentially - every n hours, your one drive should get a snapshot.

I do not think it is just "your problem." I have a late 2013 MacBook Pro and have been unable to complete a Time Machine backup with my WD My Passport since I upgraded to El Capitan. I tried all the potential fixes you did. I also reindexed my hard drive and erased my backup drive and started fresh.

The problem persists. Namely that when I initiate a Time Machine backup the process stalls permanently about two thirds to completion each attempt.