neither I nor "whereis" can find the required ppcarm (only ppcrossarm is generated after compilation). And when I try to compile something to Android I get "Failed to execute "ppcarm", error code: 127".
ppcarm won't be generated, you're building a cross compiler, not native compiler. You can't have native compiler anyway, if your host system is not arm.
Maybe there is a good step-by-step guide for fpc 3.0.0 where I can find the exact location of the libraries, or find out which installation/set-up step do I fail?
Just continue from your previous step. The ppcrossarm has been generated, but not yet symlinked to the same directory as fpc (/usr/bin). After this you'll need to make arm-linux-as and arm-linux-ld, be it symlink (I prefer this) or pure copy, from the one in NDK directory (grab any gcc version, but in my experience 4.6 and 4.9 works the best for android JB - L, haven't got M for my device so I can't test, not sure about clang version, too lazy to try) to a /usr/bin or any other directory specified by -FD in your fpc.cfg. Last but not least, make sure -Fu in your fpc.cfg can point to arm-android directory of fpc toolchain you just built above.