Rearrangement of a song means typically changing the instrumentation and/or changing the accompaniment, but normally without changing the melody. So even if the song changes character a bit, it's the same song, with the same harmony.
One of rearrangement techniques is reharmonization, when you change, sometimes quite substantially, the chords. An example could be this version of Lady Gaga's "Let's Dance" played by Dirty Loops:
It sounds quite different, but the melody feels mostly the same. In this version, even though chords are changed, the key or tonal center relative to the melody is the same as the original.
However, one can go further, and change the key, i.e. play the same notes against a different tonal center. This might be difficult for a whole melody, as good melodies often suggest a specific keys, but may work for some shorter phrases or motifs.
Then, even if you don't change the rhythm, you can place the same notes at the different part of a measure, so that some stressed notes become unstressed, some unstressed become stressed, or syncopated and non-syncopated notes switch their roles. This may change the feel of a melody by a lot.
I can't think of any examples of these two possible transformations right now, possibly because when they happen I don't recognize similarity to another melody.