Setting up and configuring a new VPS server
Solution 1:
I have never done anything like this before
To be honest you should consider hiring someone with more experience, or at least get some professional advice. Running a webserver in production involves a bit more than just installing packages (if there's any traffic) - let alone security concerns.
What linux distro should we go for and why?
Usually you should stay with the OS you are most comfortable with. Since you just started my advice is still the same but you should consider choosing based upon where you get the "best"(TM) documentation (whatever best means to you).
On the other hand if you know how to secure windows and how to run your software on it, why not go with a windows based hosting?
What are the necessary installations and configurations that needs to be done and how will I do them
- Secure your OS (SSH, Firewall, remove unneeded services, the "usual")
- Get a Testing environment - it's not clear from your question wether you have one. But you definitely don't want to deploy manually. If it's only an rsync job that does the magic it might be enough. But be sure that it's a repeatable process, be sure that you can roll back
- Since you run PHP you can only run the apache-prefork-mpm (sanely). Be sure to use that one
- Reconsider going to some provider that will do the hosting for you. It doesn't have to be shared hosting there are a couple of providers that specialize in PHP hosting and that will take for you (up to a certain point at least)
To stress the professional advice even further: If you think you save money by going with a EUR 9.99 VPS (or EUR 49.99) and do it yourself, consider this: How much money will it cost you if your service is down for a couple of hours because someone compromised your server?
Finally: Setting this up is not something for a single post here, especially if you don't have experience. A couple of people I know make a living from exactly the requirements you have and sell services just for the very reason that it's cheaper to get usefull advice and don't have downtimes instead of "learning the hard way".
Solution 2:
You should use the linux distro you know the best. The reason is for an easier user experience. New to linux? Many people say that Ubuntu has the lowest learning curve. The VPS at Mochahost.com uses a modified kernel to give you a container. The 'distro' is a set of packages that are installed to the container.
Your VPS is going to come with either cPanel or Plesk installed. Usually, Apache, MySQL, and PHP will already be installed. Using the control panel gives you a nice GUI with which you can do the standard configurations.
Come back when you need to do something the GUI can't let you.