What Could Have Been: Originally the plot was to have them visit, and therefore accidentally cause, all of history's greatest tragedies (the sinking of the Titanic, the crash of the Hindenburg, the Black Plague...).
The time machine was originally a pick up truck, then a van. It was changed into a phone booth because it might have made the movie too close to a Back to the Future ripoff. Now it's just unintentionally close to the TARDIS in Doctor Who.
Eddie Van Halen said that he would have been glad to appear in the movie, but nobody asked him.
Bogus Journey: The Evil Bill and Ted taunt the real ones by saying "Good luck getting to the concert!"...then don't follow up on it. In a deleted sequence, they use devices to re-create the boys' Personal Hells (Granny Preston, the Easter Bunny, and Col. Oates) and send them after the heroes. Bill and Ted end up having to face their fears to get rid of them: Bill gives Granny her kiss on the cheek, Ted calls his brother and apologizes for stealing his Easter candy, and both boys treat Oates with kindness and friendship rather than terror.
At the concert, the evil B&T would repeatedly kill them, but use the fact that they beat Death at so many games to get resurrected.
Chuck was originally going to die at the end and go to hell with the evil Duo, where they annoyed him for all eternity.
Word of God: The Evil Robot Usses were supposed to kill Bill and Ted at the Battle of the Bands, whereupon the boys would invoke their wins against Death to get resurrected. This part does appear in the comic book adaptation of the movie, which was based on an earlier draft of the script.