Oh really it was so simple with the magic of Collection::lists() and array_diff

$current = $user->languages->lists('language_id');
$to_delete = array_diff($current, Input::get('languages'));
$to_add = array_diff(Input::get('languages'), $current);
$min_matched_count = $to_delete <= $to_add ? count($to_delete) : count($to_add);

for($i=0; $i<$min_matched_count; $i++) {
	UserLanguage::where('language_id', array_shift($to_delete))
		->where('user_id', $user->id)
		->update(array('language_id' => array_shift($to_add)));
}

if (!empty($to_delete)) {
	UserLanguage::where('user_id', $user->id)
		->whereIn('language_id', $to_delete)
		->delete();
}

if(!empty($to_add)) {
	foreach($to_add as $lang_id) {
		$newLanguage = new UserLanguage();
		$newLanguage->language_id = $lang_id;
		$user->languages()->save($newLanguage);
		$newLanguage->save();
	}
}