Images: Rogue One Scenes That Didn't Appear In The Film Provide Possible Reshoots, Character Appearances, One Actor Signed For Another Film, And Concept Art [Major Spoilers Ahead]

Spoilers, spoilers, spoilers! Warning, there are serious Rogue One spoilers in what lies ahead. So, don't read any of this if you haven't already seen the movie. You have been thoroughly warned.
In this article we take a look at the footage from the trailers that didn't make it into the film and suggest what may have been reshot and altered from the original cut. There is also a list of characters that make appearances and concept art.
As seen by the footage from the trailers, there were numerous scenes removed or completely altered. Check them out below.

First, the words A Star Wars Story do not appear on the opening credits and the font that is used is completely different.
K-2SO tells Jyn that "The Captain says you are a friend. I will not kill you." Jyn replies "Thanks." This did not make it into the film and it appears that this takes place well after they first meet during her rescue.
One of the first trailers had a Rebel asking Jyn Erso to state her name for the record. In the film, they already know who she is and that she has been living under an alias. Furthermore, they rescued because they needed her for a mission. This scene may have been filmed solely for the trailer in order to introduce the character.
Here, Jyn utters the memorable line "This is a Rebellion, isn't it? I rebel!" It makes sense that this didn't make the cut, because in the final cut she is anti-rebellion at the beginning. Once again, this may have been shot solely for the trailer.
The remnants of a Jedha statue do appear in the movie, but it is an alternate angle instead of this one.
This sequence of captured X-Wing pilots in Jedha didn't make the cut. At this point in the trailer Cassian says "I've been recruiting for the Rebellion for a long time." In the finished version, he doesn't appear that way. He is more of a ruthless spy who finishes a mission at all costs, even if it means killing an ally.
In one of the trailers, a younger version of Saw Gerrera is delivering a passionate voiceover. The younger version of the character only makes a minor appearance, when he rescues a young Jyn. When we find him on Jedha, he is not bald and has thick layer of gray hair.
Neither of these Darth Vader scenes where in the film, either being solely for the trailers or just not making the cut.
 This sequence has a voiceover where Mon Mothma tells Jyn that her mission is to investigate a major weapons test. In the film, the mission is completely different and involves serving as the bridge between the Rebellion and Saw Gerrera so that they can recover the defected pilot.
This sequence between Vader and Krennic didn't make the cut, eliminating Ben Mendelsohn uttering the line about the "power that we are dealing with her."
This great image didn't make the cut and may have been solely for the trailer.
 Same with this one, quite possibly just for the trailer or publicity still.
 These are the major ones and indicate that the final act was dramatically altered. We See Jyn and Cassian running in the battle with the Death Star plans, indicating that either the transmission location was in another location or that they were meant to escape and survive.
 This one shows Krennic outside walking after or during the battle. The light ahead could suggest the inbound devastation that the Death Star laid out on Scarif at the end. This could suggest a totally different end to Krennic's life than what appears in the film.
This one also suggests that the transmission location was somewhere else and altered the fate of K-2SO. In the final cut, he dies helping them get the plans. This would suggest that he at least made it further than that in the original cut.
One of the epic shots in any of the trailers see Jyn walking on the catwalk at the Scarif base with a TIE fighter rising up in front of her. She still ends up on the catwalk, minus the TIE fighter. Could Krennic have been piloting it?

Felicity Jones reportedly has a clause in her contract that could bring her back for a sequel. Now that obviously isn't going to be Rogue One Part 2, because we know how things ended. But it could be in a prequel about the character or a minor appearance in the Han Solo movie. Only time will tell on this one.
Characters that made expected or unexpected cameos
Mon Mothma - Genevieve O'Reilly reprised the role that she portrayed in Revenge of the Sith, however those scenes were deleted from the final cut. 
Genral Jon Dodonna - The character was a major figure in A New Hope and returns in a minor role portrayed by Ian McElhinney.
Saw Gerrera - This character was part of a four episode arc in season 5 of the animated series Star Wars: Clone Wars.
Bail Organa - Jimmy Smits reprised the character that he portrayed in Attack of the Clones and Revenge of the Sith. He also gave a nod to Ben Kenobi and his daughter Princess Leia.
Grand Moff Tarkin - There were rumors that there would be a CGI version of Peter Cushing as the character and he ends up playing a major role in the film, while also being one of the stand outs.

 Ponda Baba and Cornelius Evazan - They briefly appear in the city of Jedha, bumping into Jyn Erso. They luckily got of the city in time to head over to have a fight in the cantina with Luke Skywalker.
Darth Vader - We knew he was going to at least make an appearance, but not how much and that he was going to kick some serious butt in the process.
C-3PO and R2-D2 - They make a minor appearance, but it makes sense since the events between Rogue One and A New Hope are so close.
Red Leader Garven Dreis and Gold Leader Dutch Vander - Instead of CGI, the original actors appeared in the film via unused footage that was available from A New Hope. Director Gareth Edwards was lucky enough to come across a set of unused film canisters from A New Hope while visiting Skywalker Ranch.
Princess Leia - Like Cushing, we end up getting a CGI version of a younger Carrie Fisher. She is only in the film for a brief time, but it is the perfect connection between Rogue One and A New Hope.
Here is some of the concept art for the film.