The difference between “We’ll ever be back to normal,” and “We’ll never be back to normal.”

Double negation is not an issue. What the mayor said was

I don’t believe we’ll ever be back to normal

There's only one negative in that sentence.
And there's only one negative in this sentence, which he didn't say, but which means the same

I believe we won’t ever be back to normal

I've boldfaced the negatives (don't, won't), as well as the Negative Polarity Item ever.
Since ever is an NPI, it's only grammatical inside the scope of a negative.
That's why another sentence the mayor didn't say, with no negative at all, is ungrammatical.

• *I believe we'll ever be back to normal

Normally negating a main verb upstairs doesn't count as negating a complement clause downstairs:

• She didn't say that he was coming ≠ She said that he wasn't coming.
• He didn't realize that she was in the room ≠ He realized that she wasn't in the room

This is called "compositional" negation, because the negative composes only with the clause it's in.
It's the norm with most predicates, as shown above. But there are a number of predicates where compositional negation is not the norm. They're all verbs of mental perception.

• She didn't believe that he was coming ≡ She believed that he wasn't coming.
• He didn't think that she was in the room ≡ He thought that she wasn't in the room.
• There doesn't appear to be a problem ≡ There appears not to be a problem.

This phenomenon is called Negative-Raising, and it is governed by these predicates only.
Unsurprisingly, these are called "Neg-Raising Predicates".

What is the difference between “I don’t believe we’ll ever be back to normal,” which is simple negation and “I don’t believe we’ll never be back to normal,” which is double negation?

In this context, the double negative would first of all be slightly confusing, but also I would say the line "I don't believe we'll never be back to normal" implies the weakened affirmative as Josh61 suggested.

That is, I would understand "I don't believe we'll never be back to normal" to mean there is a small chance the water would be back to normal in the future, if the proper action was taken.

I agree with your conclusion. A single negative is the desired form and both:

"I don’t believe we’ll ever be back to normal."

and

"I believe that we will never be back to normal."

mean approximately the same thing.

(an overly fussy person might argue that don't believe implies more concern with belief than an assessment of the water.)