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?
You could try HockeyApp to allow the users to install the application and know them about the updates. http://hockeyapp.net/features/