I think you can miss characters. Table 7.2 on page 23 of the 328 data sheet reports a typical programming time for each byte in the eeprom of 3.3 ms.
So if you get more than 1 character every 3.3 ms (assuming no time taken anywhere else), you'll have a problem.
Sending one character takes 10 bits (there are stop and start bits as well as the 8 bits in the character itself).
That would set an upper limit of 1/0.33ms = about 3,000 baud. The standard baud rate of the Arduino is 9,600 baud so no chance.
You've only got 2k of ram on an Uno too, so I don't like your chances of buffering all of it into RAM then writing to eeprom.
I'd recommend receiving the song in, say, 100 byte chunks. Buffering those 100 bytes in RAM then writing them to the EEPROM.
You could develop your own protocol for this, but you might want to look into the XModem protocol (since it is typically supported by telnet software). IIRC this protocol supports a really simple handshake where you ask for the next block of data when you have finished processing the latest. Perfect for a slow eeprom.
Alternatively, you could switch the Arduino to a lower baud rate (say 300) and send the data slowly. It would take about 1000 * 10 / 300 = 30 seconds to send 1,000 hex characters, give or take.
Yet another approach would be to use an AVI ISPMkII. Its a programmer which plugs into the ICSP connector on many Uno's and can write directly to the eeprom using a program called AVRDude. Some of the early serial bootloaders support writing to the eeprom with AVRDude as well, but most of the ones used now don't unfortunately.
Finally, we have a program called MegunoLink that lets you send serial messages. I just checked and the serial monitor has no limit on message length or you could setup an interface panel and have it send a song when you clicked a button. It is here: www.MegunoLink.com. Feel free to get in touch if you've any questions.