Finding source of WiFi Connection Failures
OK, after lots of pulled hair and bitten nails, I think I have found a solution. Rather than closing this question it might be better if I share my findings on the off-chance that someone having this problem might find the solution through google. 

First off, I installed aLogCat Root, and waded through lots of debug output. That got me 


    "Wifi connection closed with errorCode 20"


and


    "Client connection lost with reason: 4"


Googling found lots of issues, most of which obviously did not apply here, while the rest less obviously didn't. None of the solutions helped me. 

However, due to the many times I rebooted while trying all these fixes, at some point the nagging message after reboot making me aware that my Location services are disabled caught my eye and I thought I could give this a try. Well. 

I enabled Location and WiFi works now.

I confirmed it by undoing all the other things I had tried, none of which broke WiFi. However, the very moment I disable Location, WiFi stops working.

To me this isn't obvious at all, and if someone can shed some light on this, I'd be happy to get educated.