I am fairly new to Laravel, but this is a hacky thing which works:

$app =& $this->app
$this->app->validator->resolver(
    function ($translator, $data, $rules, $messages) use(&$app) {
        // Now you have $app
        // How to get an instace of $app here?
        return new RuleAliasExists($translator, $data, $rules, $messages);
    }
);

If you are using php 5.4 you can use $this->app in the closure.

$this->app->validator->resolver(
    function ($translator, $data, $rules, $messages) {
        $service = $this->app->make('Service');
        return new RuleAliasExists($translator, $data, $rules, $messages, $service);
    }
);

If running < 5.4 you'll have to use thelastblacks solution.