Not sure what your requirements are besides 5.4, but you could look at amazon web service, I believe they have a one year free of their small plan. You have to install everything yourself, they give you a virtual cloud server with your choice of OS.
You are going to need a bigger budget. Anyways, you want either a dedicated server or VPS that allows you to install your own software (PHP 5.4, Python, etc.) That will cost a pretty penny.
Many would be surprised that not all hosts are supporting PHP 5.4 at this point. You could get by with a managed VPS and that way you may not have to install it yourself if the host provides support for that through their managed VPS packages, and many do. VPS hosting is actually more affordable than many think. I also suggest that you find a true hosting company. Amazon is kind of like Godaddy in that they started out offering one thing but now they provide many products instead of one, like hosting. Seek out a specialized company for your hosting and you will find the process and services are much more stream lined and reliable.
In php 5.4 features like register_globals, magic_quotes and safe_mode are no longer available for instance, which might break sites depending on them. Please have look at http://www.php.net/releases/5_4_0.php before choosing php 5.4
Though php 5.4 has released it hasn’t been included yet by cPanel, Plesk etc. cPanel team is still working on php 5.4 to remove any possible QA issues before they include it in their latest release. For more details you can have look at http://forums.cpanel.net/f145/php-5-4-x-released-case-51392-a-261752.html