As far as I know, we do not actually see Ultron create his body. However, we know "how" he did it, even if it happened off-screen. The primary reason he went back to the abandoned HYDRA lab from the start of the movie was because that facility had the equipment he needed to create a body. He created that body in the same way he created the army of other bodies (once he got more Vibranium).
When he flees from the Avengers' mansion, he's still in a makeshift Iron Legion body. The next time we see him, the Maximov twins are approaching him in the church in Sokovia, and he's already using his new body.
Most likely, the scene from the trailer was cut due to time constraints.