Deleted Scene: Plenty, including some that were put in TV airings.
Magnum Opus Dissonance: This movie is frequently considered Monty Python's best movie, but the members themselves thought Life of Brian was their best movie.
Trope Namer: This movie has named the following tropes:
Not Quite Dead: Lancelot's "steed" Concorde, Prince Herbert, the bride's father, and a random sufferer of the plague. Also, everybody slaughtered by Lancelot at Swamp Castle gets up and joins in when Herbert's song starts playing.
Throw It In: The coconuts were originally going to be off screen due to the lack of budget for horses. The troupe had an epiphany regarding it — since the movie was nonsensical anyway, they should just write the coconuts into the script.
According to the book Monty Python Speaks they thought that the coconuts was a funny idea because coconuts are used for horse sound effects — AND had the added bonus of saving them a pound of money on horses, training, etc.
It even made it into the german title of the film: Monthy Python's Knights of the Coconut ('Monty Pythons Ritter der Kokosnuss')
Although for the most part, there was very little variation from the script, there are three instances of improvisation, two of which were done by John Cleese: The first being the pause he takes in the Burn the Witch! scene, before saying "Because she's made of wood", the second when he says Some Call Me Tim because he forgot the character's scripted mystical name, and the third being "He hasn't got shit all over him".
Terry Gilliam was originally supposed to play Sir Gawain, whose role would have consisted of repeatedly Breaking the Fourth Wall and pointing out how special effects and other aspects of the film's production were achieved. His role ultimately ended up being turned into Patsy, with his Medium Awareness jokes being toned down big-time.
Immediately after the second encounter with the Knights Who Say Ni, the original script had a lengthy sequence involving a character named King Brian the Wild, who enjoyed getting people to come to his castle, having them sing in close harmony, and then having them killed by his archers. The Knights of the Round Table nearly end up meeting this fate themselves, but Sir Robin unwittingly saves the day when he shows up in the nick of time, and the archers shoot his minstrels instead. King Brian would most likely have been played by Eric Idle, given that Sir Robin is absent for most of the sequence, though there have been some reports that the role was written for no less than Brian Blessed himself.
