Quite often this is possible without altering the melody at all. But if you consider the melody as a series of motifs and motivic variations, allowing yourself to modify them here and their, then the possibilities really are endless.
Here is dead simple melody. It is presented first with no accompaniment, then with three variations. The first is entirely diatonic, the second with tastefully subtle chromaticism, and the third heavily chromatic with some shocking twists through.
http://download.yousendit.com/C55026F7299FB8F3
Please, use the the melody and see if you can come up with any cool progressions! I would love to see how many we can come up with, kind of like a sample mash up
Or if you feel REALLY brave, you could try some polyphonic variation with the melody maybe? Whatever you like!
TB