What is the difference between the two?
The weather is not bad at all.
The weather is not at all bad.
What is the difference between the two?
The weather is not bad at all.
The weather is not at all bad.
I would use 'not at all bad' to contradict a statement that may have been 'the weather is bad', however I would use 'not bad at all' when making an initial statement.
"Not bad at all" is more colloquial speech. It's an informal way of saying that something was good, with "at all" just being an extension of the common phrase "not bad" which is, again, usually describing a positive experience.
"Not at all bad" is more formal, and tends to mean, more literally, that there was no negative aspect to something, without the implication that it was actually good. It's used to describe a neutral experience when a negative experience could have been expected.
Example exchanges you might hear:
"So... how do you like the casserole?"
"Not bad at all! Where did you get this recipe?""How was the drive? I know there is often a lot of traffic at this hour."
"Oh, not at all bad. Shall we begin the meeting?"
In your examples, "the weather is not bad at all!" would be said while enjoying a sunny day and smiling broadly. "The weather is not at all bad" would be said when you had been expecting rain, and it's actually just mildly overcast, or if you think the weather is acceptable for an activity while someone else is complaining that it's not.
In addition, "not at all bad" is much less common in American English. As an American English speaker, I cannot read it without imagining a British person saying it while smoking a pipe and discussing European Union policy decisions. "Not bad at all" on the other hand would be said by a midwesterner while slapping his friend on the back and thanking him for the cigar.
Example: Here is a European reviewing an American hotel on Trip Advisor:
“Not AT ALL bad... totally okay!”
After having read all the negative reviews, we we're very sceptical when we made an "express deal" with "price line " and got a reservation for this motel. I took my antibacterial wipes along and prepared myself for the worst! BUT ...our room was clean!! No stains on the carpet, no garbage, no sticky tables and no bad smell. OF COURSE it's no 5-star hotel but for the price it's really (more than) okay! ... Breakfast was okay (cereal, waffles, juice...).
Here is an American reviewing a Knight's Inn, from the same site, and again with the title of "Not at all bad":
The is an average property and reasonably comfortable. The rooms are better than Motel 6. All 3 front desk staff were excellent. Breakfast was limited, as advertised. Cleanliness was OK. No unpleasant odors. The A/C was much quieter than a more expensive property we stayed in the previous night.
Meanwhile, a Google Image Search for "not bad at all" returns several top images of people nodding with satisfaction or giving the thumbs up, or outright smiling.
There is a there is a song called "not bad at all" which contains these lyrics:
"How does it feel when things are going your way? You pick the lucky number every day"....NOT BAD AT ALL! "How does it feel to be #1? ... How does it feel when you feel like you should? NOT BAD AT ALL!" "How does it feel when you've got nothing to prove? How does it feel when you know just what to do? NOT BAD AT ALL!"
And for my final example, if you check out Urban Dictionary's definition of "not bad" you'll find the top answer to be this:
Fully legit. The real thing. A tasty meal is never just good, it's not bad, or not bad at all. Can always be said as 'ain't bad.' I'll tell you what, this meal, it's not bad. It's not bad at all. Mmmm.
There's a definite but subtle difference between "not bad at all" and "not at all bad", and it has everything to do with the phrase "at all" and which word it's acting on. This phrase is used for emphasis to convey a sense of degree and means "in any way or to any extent" (Concise Oxford, Australian edn 1987).
In both cases, the general meaning is the same: the weather is okay. Using the two negatives "not" and "bad" together suggests a sense of grudging admission or even surprise - so the meaning becomes something like "the weather is better than might have been expected." The phrase "at all" then qualifies the statement.
In the first case, the word being acted on is "bad". In the second case, the word being acted on is "not". Putting the emphasis on one rather than the other conveys a very subtle difference, which I find quite hard to pin down. My best explanation is that saying the weather is not bad is less emphatic than saying the weather is not bad. The phrase "at all" simply acts like putting the target word in italics.
So: in the first case the meaning is something like "the weather's okay, surprisingly" while the second case means something like "the weather's really quite okay."
I largely agree with EA and Dr Q. In England 'not bad at all' is the typically understated way of saying 'quite good', or 'quite reasonable' (former more for things, latter used more for situations).
'Not at all bad' tends to mean that one expected something (or some situation, event), to be bad, but it is not.
I would question Dr Q's resorting to Urban Dictionary for his final examples. UD has no standards at all, is full of joke definitions, and in any case many of the definitions are non-standard, regional etc.