Natanavra,
You're correct the map for each mission is built at runtime. I have a seperate layer for movement like you said. The terrain for each mission is about 5000 px wide I can go up to 10,000 px too. First, I create the cp segment shapes for collision detection and then I build out the terrain graphics using cocos2d. For example, if the terrain is 5000 px wide, I load 5 1000x320 graphic slices and align the graphic slices in my game layer to match the cp segment shapes. The background is just another layer I put behind the game layer.
For scrolling the map I simply move the entire game layer( 5000 px wide ) by calling the setPosition method in every step based on the x position of the vehicle. Here's what I use
CGPoint tempPos = [ self position ];
[ self setPosition:ccp( -(chassis->p.x- xScrollOffset ), tempPos.y ) ];
I haven't tried using the camera.