Any music published before 1922 in the United States is in the public domain (however no knew works will enter the public domain until 2019 due to a change in the law). This means that the song is free to use, not any particular instance of the song.
Any recording of a public domain song is copyright by the entity (usually the performer or producer of the work). This means you can’t use this particular waltze without pemission (and it doesn’t make a difference if it’s a MIDI piece producted by some unknown or a full orchestra piece by the London Symphony Orchestra).
As was mentioned earlier, most popular music in the public domain has a representation of it that the performer has declared to be in the public domain. These are easy enough to find on a web search.
If you can’t find it, then you can always get a copy of the sheet music and enter it yourself (and if it’s really complex there are programs out there that can scan sheet music and create the MIDI). Then it becomes a work that you can copyright as the performer.
Take a look at http://www.pdinfo.com/copyrt.htm for more info.