The story was told, memorably, by Gerard Hoffnung (to the Oxford Union, in 1958), which predates any of the sung versions as far as I'm aware. If you google Hoffnung and Bricklayer you'll find it started life earlier still - possibly 1937 as an urban legend.
I even had the great pleasure of hearing it re-cast in a story we were co-creating in a storytelling workshop in Dartmoor Prison - the man concerned obviously knew and loved the way the story flows and found a way to incorporate it.
Sung or recited, it's a great story and always funny.
Anne