How about a "lean-to". You only need 4' wide and no more than 5" tall. If you just put a small 1/2 roof off an exterior wall and framed it in, you would have ample storage.