Barendd Nobeard said:
I also remember other verses: "build it up with iron bars" and "iron bars will bend and break" and "build it up with silver and gold".
I have a great book - "The Origins of Rhymes and Songs" by Jean Harroween - which details several different verses, including mud and clay, iron and steel, silver and gold, and stone so strong (but no salt and pepper!).
There is also an (original?) variant from the Norse Sagas which begins "London Bridge is broken down" which tells of the Vikings ripping down (the then wooden) London Bridge in 1014. The bridge has fallen or been torn (or burned) down several times over the centuries (since the original Roman bridge) and been rebuilt with more modern materials. It also notes that in earlier times, human sacrifices were sometimes walled up within bridges to guarantee the water spirits looking on the bridge favourably (a child's skeleton was found in the remains of a bridge in Bremen, Germany, in the nineteenth century).
My memory was always "London Bridge is falling down" but the book refers all the time to "London Bridge is broken down". UK memory, there (50 miles north of the bridge itself!)