(Rhetorical) What kind of apps force their users to go through captchas? Sheesh!
I screwed up my update, so i too started on a clean 3.4, and upgraded to 4.0 before installing the Android Runtime.
Installing microG works just as well as before. (no idea if it supports captchas, and not intent on finding out)
So, either just grab the APKs off their site, or add their repo to F-Droid and install through there.
Enable signature spoofing in settings (understand why, blablabla), and don’t forget to symlink /home/nemo to /home/defaultuser and it should work.