We do have PHP5.2 available on our servers and our LPCP servers include an autoinstaller for Drupal under Webapps. Yes it does run here.
Yes our shared plans have Apache mod_rewrite module.

Most, if not all, servers with PHP 4 + 5 have PHP 5.2.x. When you click the "upgrade" button, it will put a line or two of code in your .htaccess file, to tell the server to use PHP 5. Note that your cPanel (if that's what your server is using) will still claim it's PHP 4 -- run the following:
to confirm that it's actually running PHP 5.2. If the server is still at 5.0.x or 5.1.x, open a support ticket to either get the server upgraded or be moved to another server with 5.2.

Most new shared server accounts are on servers running LPCP, LP's home-brew control panel. Other accounts use the commercial cPanel, which is being phased out at LP. If you have cPanel, that's fine -- no need to change anything. On cPanel, use "Fantastico" to install applications.

I have no idea what's involved going to a VPS or Dedicated server. You have more input (and responsibility) about what levels of PHP, etc. are running on your system.

OK, if Fantastico (a third party installer) doesn't have Drupal, you'll have to go to the drupal.org site and download their install package. It appears to be a .tar.gz file. If you don't have the tools on your PC to uncompress (gnuzip format) and untar it (then upload the unpacked system with FTP), I would think that they would exist on the server side (upload the .tar.gz file, run command-line tools to unzip and untar it, according to Drupal's instructions). Not quite a "one click" experience, but one way or another it should be possible. If cPanel doesn't directly offer the tools, you may have to run the unzip and tar commands via a cron job. If you can't find the tools, put in a support ticket and they can tell you where stuff is.