Try checking out required_without_all:foo,bar,..., it looks like that should do it for you. To quote their documentation:

The field under validation must be present only when the all of the other specified fields are not present.

Example:

$rules = array(
    'facebook_id' => 'required_without_all:twitter_id,instagram_id',
    'twitter_id' => 'required_without_all:facebook_id,instagram_id',
    'instagram_id' => 'required_without_all:facebook_id,twitter_id',
);
$validator = Validator::make(Input::all(), $rules);