1: My current POD (based on a very cursory research) is that Caliph Al-Hakam II has a son earlier in his life, and he takes the reins of goverment instead of his Grand Vizier Al-Mansur (Al-Hakam aparently was homosexual, so he had a son late in life. Since his son was 11 at the time of his death in 976, his vizier took power, bringing a civil war and the slow decline of the Umayyad Caliphate). Either that or his vizier never reaches power. Is this plausible? Where other personages or forces wanting power on Al-Andalus or would most people accept this caliph as legitimate?
The problem is that Al-Mansur is representative of the rize of a "foreign" military class in Al-Andalus. Not only he was very close to Al-Hakam (being his tutor for some years). If the expedition in Maghreb isn't butterflied (I don't see how it could be), Al-Mansur would still increase the number of berbers in the army and therefore its own power.
Al-Mushafi couldn't really stand with the constant need of the caliphate to rely on mercenaries from Christian Spain or Berber Maghreb. Not talking about multiple factions : berbers, muladi, arabs, etc.
Al-Andalus suffered hevily from its "ethnic" fractionment.
Furthermore, during the dictatorship of Al-Mansur, for everyone the Caliphe WAS the authority and Al-Mansur tried to preserve the apperance (while his son and sucessor tried to have the appearance of power as well and failed totally).
2: How to deal with the North Africans? Over the history of muslim Spain, they were often called by caliphs and taifas as military help, and they took power themselves, thus weakining them against christian kingdoms. I'm thinking of a peaceful integration with the rest of the caliphate, but is a military conquest plausible?
No. Al-Andalus was in constant need of soldiers and mercenaries. If they didn't came from Berber Maghreb, they used Christian from northern states.
North Africa was therefore seen as both a buffer region against Fatimids/Zirids AND a reservoir of men.
The Cordobans had interest to keep this region weak and divided enough to keep control of it and avoid the use of the Berber by one of the statelets. Integrating it would have meant : more importance of Berber princes and weakening of caliphal power + existance of two "hot" fronts : north and Africa.
For a military conquest...The operations were already hard to do WITH the support of Berber rulers so with a direct opposition of every of them...
3: Would European powers launch a crusade against Al-Andalus if they became too sucessful? How would both sides fare?
You had regular campaigns of christian princes with the help of occitan or frankish nobles, some of these being pre-crusades, preached by the popes and with a clear religious goal (if totally mixed, and assumed, with territorial concerns).
So, the European powers would do just what they always did : little wars, little campaigns eating little by little the margins of the caliphate. They have time, more stable institutions, more ressources and more support from their neighbours than the caliphe would never had from its own.
Now, if we're talking of a large scale crusade after a sucessful taking of Jerusalem...Here's the role of kings and princes would be more important : don't forget that the one of the most important leader of the 1st Crusade is Raimon of Saint-Gilles at the image of the power of great princes in southern France and Iberic peninsul.
So, you'll have both more ressources and maybe more men (we're not talking of taking a city at the other edge of the sea, but a land next door, with known terrains thanks to earlier campaigns and raids) but aslo more conflicts between crusade leaders.
The "I won't give a shit about what happen to my neighbour"-effect, famous during 1st Crusade would probably apply there, just less importantly. The clientele or great lords of Andalusia would probably help the Caliphe, but serching a way to negociate more power for them and peraphs a peace with crusaders if things turn wrong.
Preventing Al-Mansur rise and especially the sacking of Compostella, one of the most important pilgrims and religious place of medieval Europe, would certainly help.
4: I think that, given a surviving Al-Andalus, the muslims, christians and jews on Iberia would become used to live togheter, and a more tolerant culture than that of most of Europe would develop. Any interesting cultural changes you can think of?
You think wrong, sorry.
First, what do we call tolerence there?
If it's the modern idea of "I don't give a shit about your religion, convictions, origin, let's be pal"...Forget it, it didn't existed, nowhere in the Old World before the XVIII century.
If it's the idea of "Ok you're different from me, but instead of persecuting you, your family and force you to flee or convert, I'll just consider you as a second class citizen with less rights and more taxes to pay", that was relativly well present not only in Arabo-Islamic world but Christian world as well.
You had important jewish communauties in southern France by exemple, not getthoïzed and having their own representatives (Kalonymos, "king" of the Jews of Narbonne by exemple).
Of course the situation is changing : periods of cohabitation (with even Jews with charges of power over Christian or Muslims), suspicion (the usual) and pogroms and slaughters (Worms, Grenada).
The Almorvids would be so tolerents that many Jews would prefer join the king of Castille force.
So again, tolerance in a modern way? No.
At best cohabitation in favourable times, suspicion and second-class feature as the norm and attacks and pogroms as reaction during crisis time (Fitna, epidemics) or from opportunist (low german nobility, berber invaders).
For Europe the situation began to be really hard for Jews between the XIII and XIV centuries. In one century you pass from suspicion or even cohabitation to exile.
For Al-Andalus, the fitna provoked many anti-juadic actions(anti-jewish religion, not anti-semitism that don't care about religion but about race, ultra-minoritary during MA). The most popular states and rulers were the most djihadist ones, the most "rigorist" when it came to application of charia.
Of course, the Jews in Al-Andalus were only one of the dhimmis "minorities" (Christian being the other "minority" representating only 1/3 to 3/4 of the population depending of regions) so protected by that when in Europe, Jews were THE minority and more or less assimilated to heresy features with the XII century putting their situation more precarious.
You coul prevent that with a living caliphate, but not only it would be REALLY hard to make it but before the rise of christian principalities and the "I'm more pure than you-game" between Muslims princes...
5: Finally, the big question: Could an Islamic Spain discover/colonize the Americas, Africa or Asia? How would they treat the natives?
Al-Andalus benefitied from the trade with Sudan (Mali, Ghana) and could try to place trade centers along the west african coast (while it would certainly provoke a rivality up to war with berber states such as Almoravids or sucessor) without too much direct benefit at short term.
Americas? Asia? Why not about discovery but what would have been the point of going THERE? It's not like you'll have a great motive : spice road not blockaded, trade with Africa most obviously beneficial.
Treatment of the natives? Slaves took from their lands, sent to Al-Andalus then islamized and arabized if not already. While trade centers are possible, I don't see many motives to go deeper in the lands : probably they would provoke the apperance of buffer states to protect these centers.
After colonization, converts would be treated as equals, while non-converts would probably be either killed or more probably reduced into slavery.
Berbers and Muladi treatment by the Arabs in Al-Andalus would rather indicate the existance of another second-class people, more or less metissed.