I am running the latest master version of MediaWiki and VisualEditor. I installed Parsoid according to the instructions in <https://www.mediawiki.org/wiki/Parsoid/Setup#Ubuntu_.2F_Debian_on_amd64>. Everything is configured correctly, but VE can't communicate with Parsoid (404).
Reverting f5c874cbaf2c1408342305fbc87dc6db36728e07 locally fixed the issue; apparently that patch makes MediaWiki incompatible with older Parsoids. I conclude that the Parsoid in the apt repository is hopelessly outdated; please update it.
A side note: configuring it according to https://www.mediawiki.org/wiki/Parsoid/Setup#Configuration causes the Parsoid service to be unable to start, since `parsoidConfig.setMwApi` actually takes two arguments and not one. I don't know if this is a typo in documentation, or another symptom of a hopelessly outdated version.