Phalcon can be installed on any machine on which the hosting provider offers SSH root access (or sudo). Below is a list of reputable companies that offer such services:
Fortrabbit

Fortrabbit

Fortrabbit offers many hosting plans (there is one for developers and is free - with some limitations) that would satisfy the needs of most of the developers that wish to either try Phalcon or deploy their applications using it.

They offer a variety of extensions that would satisfy even the most demanding project.

Stable versions of Phalcon are pre-installed, you can activate them from the administration dashboard.

Digital Ocean

Digital Ocean

Blazing Fast Cloud Technology. Built for developers. Deploy an SSD cloud server in 55 seconds. See more

Install Phalcon using the standard instructions of installation.

Follow this tutorial to get started

Layershift

Layershift

Next generation, auto-sizing PaaS for Java, PHP, Ruby, Python, and Node.js apps. Fully isolated self-scaling role-based containers for each customer, including choice of Apache or Nginx, and full range of SQL and NoSQL servers. Pay for resource usage, not server instance size. SSD-powered. UK hosted.

Follow this tutorial to get started

Windows Azure

Windows Azure

The Windows Azure cloud provides you with highly scalable and manageable Windows hosting for your web apps. Use Phalcon to reduce your instance costs.

To install Phalcon, follow the step by step procedure in this SitePoint article.

Amazon EC2

Amazon EC2

Amazon Elastic Compute Cloud delivers scalable, pay-as-you-go compute capacity in the cloud.

Select a pre-configured, templated Amazon Machine Image (AMI) to get up and running immediately. Or create an AMI containing your applications, libraries, data, and associated configuration settings. See more

Install Phalcon using the standard instructions of installation.

Linode

Linode

Deploy and Manage Linux Virtual Servers in the Linode Cloud. Get a server running in seconds with your choice of Linux distro, resources, and node location. See more

Install Phalcon using the standard instructions of installation.

WebFaction

WebFaction

WebFaction Hosting for developers. Full shell access to fast servers with all your favorite tools pre-installed and maintained for the user.

To install PhalconPHP in WebFaction, follow the instructions outlined here

Rackspace

Rackspace

Cloud Servers are virtual machines running Linux or Windows® Server in the Rackspace Cloud. You can scale resources like CPU, memory, and storage up or down, depending on your needs. Best of all, you can pay as you go. See more

Install Phalcon using the standard instructions of installation.

hosting_aspnix_title

hosting_aspnix_title

ASPnix provides superior Windows web hosting services. Our customers have rated our service as outstanding. We offer economical plans for shared Windows web hosting, Virtual private servers and dedicated servers! See more

Phalcon is supported on all Windows shared web hosting packages and plans, no configuration or installation required! They offer a variety of PHP versions from 5.2 – 5.6 as well as many additional extensions!