The Musical Traditions article Birmingham Ballad Printers gives us 1840s?-1861 for printer William Pratt, and the article J.T. Wood on the Strand says that "at least by January 1858 [Woood's] principal address was at 278 Strand."

Combining both ranges we would have a possible print date for Everybody's Song Book in 1858-1861.