Yes, this is possible. I did something similar, until I realized that subdomains really ain't that great (for me) and a first-level route is better. Anyways, in your apache configuration you'd do something like this for every "main" subdomain:

<VirtualHost *:80>
                ServerName staging.sitename.com
                DocumentRoot /var/www/staging/public
                ServerAlias *.staging.sitename.com
                SetEnv MY_LARAVEL_ENV "staging"
                <Directory /var/www/staging/public>
                        <IfModule mod_rewrite.c>
                                Options -MultiViews
                                RewriteEngine On
                                RewriteCond %{REQUEST_FILENAME} !-f
                                RewriteRule ^ index.php [L]
                        </IfModule>
                </Directory>
</VirtualHost>

Then at the top of your route file, you can grab the environment you set with apache above. Something like this for different main domains:

if (App::environment() == 'staging')
{
	$domain = 'staging.sitename.com';
}
elseif (App::environment() == 'live')
{
	$domain = 'sitename.com';
}

Route::group(array('domain' => '{company}.'.$domain), function()
{
    /* put your routes here */
    Route::get('/', 'YourController@getCompany');
});