Can I rename index.php?
Others have advised you not to do this. I too remain in that idea, but to answer your question:

Can Drupal even run without index.php? Can it be a different file name?

Technically it's possible for Drupal to run on any different directory index file name. But you need to configure your web server for that first. Unfortunately you will need to hack core as well, which is considered without-doubt a bad idea.

.htaccess changes

Assuming you are using Apache, and because it can automatically detect http://example.com?q=node and http://example.com/drupal.php?q=node if the DirectoryIndex drupal.php, you will only need to change the .htaccess file. 

if your web server is not Apache and if you can't configure it to above URL patterns, you have to modify line 1518 in common.inc as well (Drupal 6.31). 
Things will get much complex in Drupal 7.x. You will have to make several hacks which you will find difficult to maintain patches for. 

In your .htaccess, change these (using "drupal.php" as the new file name). 


ErrorDocument 404 /index.php to ErrorDocument 404 /drupal.php
DirectoryIndex index.php to DirectoryIndex drupal.php
RewriteRule ^(.*)$ index.php?q=$1 [L,QSA] to RewriteRule ^(.*)$ drupal.php?q=$1 [L,QSA]


You will probably need to modify your unit tests and shell scripts as well.