Aside from Webfaction or Fortrabbit as a Phalcon's Web Hosting which other server providers do you recommend?
Is it okay if I choose HostGator's Virtual Private Server?
You can choose any host you like, so long as they allow you to use su or sudo to install the extension. By the sound of it you shouldn't have any issues with a Private Server :)