What I'd like help with is advice on whether adapting old melodies will improve composition skills and maybe lead to something more 'original' in the long run.
Yes, but compositional skill is the goal, as apposed to a focus only on melody, you should not only look at melody and it depends a lot of what "adapting" involves.
One approach is to abstract a specific existing work down to a structural level and then re-work that structure into new surface level detail to produce a new work.
You can abstract various things...
- phrase structure, ex.
\\: I ... V (H.C.) :||: I ... V I (P.A.C) :||
- harmonic progression, ex.
V65/IV IV V65/V V
- melodic outline, ex.
^4 ^3 ^2 ^1
When deciding on surface details you can choose from many palettes...
- conjunct v. disjunct motion
- chord tones v. non-chord tones
- change meter
- harmonic rhythm
- metrical displacement of events
- rhythmic figuration
...and many other things.
...I normally start with chord changes and try to sing something over them...
This is an example of the approach I described. If you don't like the melody that results, start digging into melody analysis. You really need to move beyond harmony textbook type analysis to do that. You need to analyze scores beyond chord progressions only. Your music theory reading should expand accordingly.
I suspect pop/jazz is your main interest, but because it's hard to find good reading material specifically on melody, you may want to expand to "classical" sources. On thing to look into is the historic melody teaching material called solfeggi, which taught melody via exemplars.
...Is it OK just to steal great melodies or parts...better to adapt something really good to my lyrics...
I assume you mean you have lyrics and then you find existing melodies that can support your lyrics. This is something different. It's either pastiche or something like vocalese. That seem more suited to a lyricist who wants to quickly flesh out some music without collaborating with a musician. That may provide placeholder type music, but I don't see that it helps much to learn composition.
...improve composition skills and maybe lead to something more 'original' in the long run.
It might be better to worry less about originality with this kind of study and instead focus on expressive outcome of each exercise. For example, take a tune like Over The Rainbow, keep the same rhythm and general melodic contour, but change the size of each melodic interval (this could involve a change of mode.) Do three such exercises, then compare the results with each other and the original melody. File it away when finished. Forget about the three exercise melodies. Remember the expressive effects achieved. Don't worry if they are original.