Recently a video of Beck playing an in-store performance at a record store in Atlanta appeared on the record store's website. Not sure the exact date, odds are it was around March 23 or 24, 1994, during the first weeks of the Mellow Gold tour.
The first song they play is a stomping blues jam, with Chris Ballew on slide guitar. Beck adds some harmonica. He also sings into some weird microphone/dustbuster-type contraption which distorts his vocals. It feels to me like something they just spontaneously played, and not something that was formally written. But who knows with this early stuff.
At the end of the song Beck says something like "thanks for coming! It's called 'Frat Rock'!" Thus the title was attached to the song they just played by the videographers, and then by us, here, now.