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: When the Evil Bill and Ted said they would have a hard time getting to the concert, it was because in a deleted scene, they made their fears (Colonel Oats, the Easter Bunny, and Bill's Grandma) come to life. To defeat them, Bill willingly kissed his grandma, Ted apologized to Deacon for taking his Easter candy, and they both show Oats love.
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.
