Dave and Rich,
I think your best bet is stenciled clouds, though I fear that you have already boxed yourself in to get to the walls. I have built two layouts. One I used a roll of darkening window shade material that I bought at a 50% off sale at JoAnn's. I then hung it over wood-like paneling. I had a very talented Mother-In-Law who painted the waterfall scene in he middle, but I painted the sky and the clouds. I have had to rebuild. In my new location (the old home that I grew up in) I just painted the block walls azure blue in the basement and then stenciled clouds all around. The stencils I bought back then are made by New London Industries. You can do all kinds of clouds with them and then you can add your own wisps. I also would go over some of the white clouds with a bit of gray to give a more realistic appearance to them. If you search for New London Industries, you can find several suppliers. Here is one: http://www.blueridgehobbies.co...stries-Main-1-10.asp.
Here are a coup;e of pictures of the cloud formations that you can create (and be mindful, I do not have an artistic gene in my cells!!!!)