For reference, what you are referring to as "parent" is usually called the root directory, or just /.
That all sounds like the normal setup for shared hosting. Most programs are in /usr/bin (or a few other more obscure directories), but only the system administrator can add things there.
Programs can normally be anywhere, but if they arent in the normal directory, you have to type out the full path name instead of just the program name.
The one extra thing is the program has to have the execute permissions in order to run as a program. You can change a program permission with the chmod command.
Some shared hosts dont let you run custom programs (perhaps via selinux rules or something), so that's a possibility that may or may not apply to you, although most hosts do allow it.
If you enable the mediawiki debug log (see How to debug) it should include what it tried to run and errors encountered which might help with debugging.
There are also many different types of linux. If you got precompiled binaries, its possible you have the wrong type. I would try running these commands with the full path ( so if binary is in the site directory, typing /home/site/pdfinfo ) from ssh to make sure the programs work.