First things first - Never ever set 777 on any folder that can be accessed via a script or a web browser. Make sure you roll back your permissions to what they should be 644 for files and 755 for directories with 775 for Laravel Storage folder.
Your servers is using Apache correct? Knowing that let's start some troubleshooting. What does your VirtualHost file look like? Is it setup for the correct document root and does it include index.php as an index file?
You can test this by explicitly typing index.php at the end of your URL...for example http://mydomain.com/index.php. If you get the Laravel Welcome page, then it's a good sign that index.php simply is not setup as an index file.
The other thing to check is to make sure the .htaccess file was imported from GIT (or even committed to GIT in the first place) as it sets up Clean URL's.
Are you on dedicated (or virtual server) hosting, or shared hosting? If you are not on dedicated (or virtual server such as DigitalOcean or AWS) then you need to check that you have the correct versions of everything installed. In fact that's a good idea regardless. You say you had phpinfo() to run...what version of PHP is running? Do you have MCRYPT extension up an running (if on a shared host mcrypt may not e setup).
One thing I would love @TaylorOtwell to add to a future version of Laravel is just a simple test.php file that can be loaded that simply checks if the server meets the basic minimum requirements to run the version of the framework (such as version of PHP, check that .htaccess is there, check that folder permissions are setup correctly, check that mcrypt is setup, and I think that's about it).
Give us a post after running through these instructions and let us know what the result is and we can go from there.