To avoid the two-scenes-in-memory problem you can simply add an intermission (loading) scene in between that does nothing but display a "Loading" text or graphics. When you switch to the loading scene the old scene has time to deallocate before you load the next one.
You can also cut texture memory usage in half by reducing color depth from 32-bit to 16-bit. Particularly on Retina images the difference with proper color dithering is hard if not impossible to make out.
Also you can load textures in background using CCTextureCache's loadImageAsync method. But you'd still have to wait for the texture to be loaded before you can create a sprite using that texture, so you don't really win anything there.