While looking into the more common "penny trick" I found most posts were in the form of: "Don't EVER do this!" Seen as a quick fix "life hack" to stop a needle from skipping audiophiles condemn this behavior because of the potential damage to the needle and record.
This Colored Vinyl Records Blog post details why this "penny trick" is a bad idea:
"Adjustable counterbalance is an essential feature to look for when choosing a record player. Usually this is a rotating tonearm counterweight with which you can independently adjust the tracking force of your needle (the amount of vertical pressure keeping your stylus against the surface of the record). Precise tracking force is important for the quality of sound and to prevent damage to your stylus and your records. If it's set too heavy, your stylus will be too light and will cause the record to skip. If it's set too light, your needle will be too heavy and while it will track your vinyl well, it can cause damage to the grooves of the record."
A few people said that you could use a penny to add to the mass (not the weight) of the cartridge and stylus end but it would have to be appropriately counterbalanced on the other side. I found no mention of changes in frequency; but many report better tracking of the stylus.
I remember my dad's record player had a switch for playing a few standard speeds for different size records: 33.3 rpm, 45 rpm and 78 rpm. If you accidentally used the wrong setting you either got a very low Barry Mannilow version or it sounded like the Chipmunks. [More on the concept can be found in this Popular Science 1950 post about how to make your own variable frequency generator so your old turn table could play newer records.] My best guess is that as Barnes weighed down the stylus with quarters he was causing it to dig into the record enough to slow it down. This caused the frequency to drop as a function of the speed change but not enough to hear a tempo change in the song.
The exact frequency of an E# depends on the octave of the instrument you're playing. According to this diagram of frequency vs position on treble clef (name of note) there is not much of a frequency difference between the two. From mid E to F (same as an E#) the frequency rises from 330 Hz to 350 Hz. From a D# (same as an E♭) to a mid E the frequency rises from 310 Hz to 330 Hz.
What does that sound like? Here are two seconds each of 310 Hz to 330 Hz to 350 Hz so you can hear the shift.
How much did Barnes record slow down then? I can't put quarters on my dad's turntable to repeat the experiment; I might be disowned. But I can play with the speed a record is played at. My next step is to play a record with hopefully a pretty constant frequency at the different rpm settings and measure the changes in frequency.
Any other insight into this would be appreciated in the comments.
EDIT: Thanks to Al Sefl of San Francisco for sharing that there is a direct relationship between the frequency we hear and the speed of the turntable. Running a 33.3 rpm record at half the speed results in half the frequency. Therefore dropping the 350 Hz E# to the 310 Hz E♭ could occur from dropping the 33.3 rpm to 29.5 rpm or so. So it is conceivable that the additional weight from the quarters weighed the stylus down enough to drag the record and slow it down. Still not a great idea.