Big company X provides its employees with Android phones. Those employees don't necessarily own a Play Store account (gmail address required AFAIK).
At the moment, my alternative is to send a link to our .apk file, however the installation procedure might be quite complicated, not even mentioning the updates.
What's the best way to deploy my app to these phones?
Uchiha Madara is right, but it's not very convenient. They can also subscribe to Google Apps for Business ! Besides, if phones are Lollipop phones, you can very easily enable Android For Work, with pretty useful features to controll mass-hardware !
However, it's not the unique solution. You can self-host your apk file as you do, make a webservice and make your app able to communicate with to check updates ! The only problem is to teach users how to allow install from unknown sources (in security settings), which may be hard if they aren't very confortable with Android phones.
Other solution, some companies offer whole turnkey solutions, like PushLink