Rather than create my own software, can I just take existing GPL software and provide a cloud service around it? Will that be legal?
You can indeed. GPLv2 and GPLv3 only require that you distribute the source code when you're distributing the binaries. In the case of software-as-a-service you're not distributing binaries and, as such, you're under no obligation to distribute your source code either. This is sometimes referred to as the SaaS loophole
Yes, the GPL is a free software licence, and one of the properties of free (as in freedom) software is that you can use it for anything, including providing commercial online services.
This is not only legal; it is common. Ángel’s answer provided some good examples. A comment on the question mentioned the LAMP stack (half of which – Linux and MySQL – is GPL v2). Other examples are KVM, which is licenced under GPL v2, and OpenVZ (which is apparently GPL v2 as well, but it is split over many repositories so I have not verified this), both of which are used to provide VPS services.
There is one thing you should watch out for: the Free Software Foundation also released a licence called AGPL (Affero General Public Licence), which is similar to the GPL. It adds a requirement to distribute (on request) source code to users who interact with the software over a network, even if those users never receive a copy of the object code. The AGPL addresses the concern you raised in your comment on the other answer, about people locking up GPL’d software.
There are three general flavours of the GPL around:
The AGPL forces you to hand out source code to any user of your software upon request. For the AGPL, it doesn't matter, if the users downloaded the software as a binary to their machine or if they use it over a network on your server.
The GPL requires you to hand out source code only, if you provided a binary. For software running on a server, you don't need to provide source code.
The LGPL is the least restrictive: If you use LGPL code in a project, and distribute binaries, you only need to provide the source code of the LGPL parts, and the ability for the user to run the binary even after updating / upgrading the LGPL parts. This requirement is usually fulfilled by dynamically linking against LGPL libraries.
So, in your case, where you want to run a proprietary cloud service based on free software: Yes, you can do that with GPL software, but not with AGPL software.
Please keep in mind, that GPL and AGPL are infectious: If you have 500,000 lines of your own code and 5,000 lines of GPL code in a project, the whole joint work is still GPL. And if there are 1,000 more lines of AGPL in that project, it will even be AGPL.
LGPL on the contrary does not take over your code: You may link against LGPL libraries, most notable Linux/GNU libc, and don't loose any rights to your proprietary code.
Yes, you can. You can for instance provide a machine running a Linux kernel (GPLv2), with a web server using GnuTLS (LGPLv2.1+) and a web site built on Wordpress (GPLv2+).
From a business point of view, you should however take into account whether that is accessory or the main value of your service and which additional value you are providing.
For example, it would seem unlikely that a custom OS you coded from scratch performed better than using Linux (or other existing OS), and the actual OS is unlikely to matter for the service you will be providing.
On the other hand, if everything you provide is available by existing software (which is perfectly fine), you should mind which value you are providing versus your competition. Do you offer local support? Is it part of other services? Do you have a better expertise than other companies? (e.g. Automattic employing the main Wordpress developers) Are you much cheaper? Your business may flourish without any of them, but you may then rely on an higher demand than provided by the competitors which provide more value (however that is perceived by your clients) than you.
Although more noticeable when using FOSS, note these are things you must mind as well even if everything you offered was your own proprietary code. You may have built an acceptable blog software, but a competitor using Wordpress (and thus with less investing) might be providing a service as good or better than yours.