"I do not believe that he is going to come with us."
Translation:Ich glaube nicht, dass er mit uns kommen wird.
The word order is incorrect. But it's a pretty tricky construction combining a few things. Let's take a look:
"He comes with us" = Er kommt mit uns
Normal present tense sentence, with the conjugated verb in second position.
"He is going to come with us" = Er wird mit uns kommen
Here we have a sentence in future tense. To make the future tense we have the helping verb werden in the second position, conjugated to match the subject (er wird). The full verb goes to the end, in the infinitive ('unconjugated') form.
"I don't believe that..." = Ich glaube nicht, dass...
This is the set-up to a common grammatical construction called a subordinate clause. This is like a sub-sentence inside the main sentence. The word order rules for subordinate clauses are different to main clauses: The conjugated verb goes to the end. But we already have a verb there? Well, subordinate clause rules are stronger, so that gets bumped to second-last position.
"...that he will come with us" = ...dass er mit uns kommen wird
You can see that this is the same word order as our earlier example, except with wird picked up and moved to the end.