As the title says, I would like to deploy my application on multiple phones, without developer unlocking them.
The said application is private, thus it can't be distributed through the store. I've heard of Company app distribution, however it's not clear for me whether it requires a developer unlocked phone or not.
Can you tell me how can I get custom apps on WP8.1 phones, without dev unlock?
The link you have shared describes steps to distribute app internally.
For deployment of company apps developer unlocked phone is not required. Once company app is ready for deployment, you need to install .aetx file which is generated form the code signing certificate. .aetx file can be shared to users through mail which can be accessed through phone to install. Once this is installed you can deploy xap by just clicking on the shared xap file. sharing can be through mail, dropbox, or any secure website.
Let me know if more doubt.