Composites of Immiscible Solids - Aluminum and Lead Example
You are correct that solid Al (fcc) and Pb (fcc) are (surprisingly for both being fcc) not miscible in each other (well, there is always some miscibility as driven by entropy). Heck, there is even an miscibility gap in the liquid phase as well. Al and Pb really don't like each other. 

So, as you cool the liquid from above 1418C (the top of the liquid miscibility gap), you will phase separate in the liquid phase. At the aluminum melting point, the aluminum will solidify, and the Pb will remain liquid. When the Pb melting temperature is reached, the Pb will solidify. The exact specifics of the solidification will depend on how it is done (the kinetics), not the thermodynamics. This means you can't predict the final micro-structure without  details of the process.

The final result will be solid Al and Pb, likely intermixed. It is not an alloy, but a two-phase mixture. I would not call it a composite as I would generally reserve that name for actual composite materials.