When you paste over a selection in Vim it will replace the default register with the contents of the selection. If pasting over a selection is wiping out the contents of the clipboard register then very likely you have the following line in your .vimrc
set clipboard=unnamed
One option is to remove that and use the explicit clipboard register "+
Another option is to use any of the other explicitly named registers (a-z). After the first paste yank the line back into "c for example and then use "cp to paste from there on out.
(note: this will work only with the default register, but this mapping is easy to remember). Writing a more elaborate version would be possible. Also, you still can use P to get the old behaviour.
"0 should have the contents of your yank. It's a bit more tedious to type, but "0p should do what you want.
Alternatively, don't select-and-replace the old lines up front. If you find those lines with a search, just hit n. over and over (after an initial p), then when they're all pasted, do ndd followed by as many n.s as necessary.
The biggest mental switch I've needed to make when moving to Vim is to figure out how to apply group edits sequentially. I.e. rather than doing a bunch of edits on a line and then doing a bunch of the same edits on another line, I'll do the first edit on a bunch of lines (using . to great effect), then the second edit on a bunch of lines, etc. Alternatively, the use of macros may help as they are fantastic, but sometimes a little more tedious to get working correctly with "complex" changes.
Instead of using copy/paste, it is often better to use a text object command such as ciw to change the inner word. This method has the advantage of being easily repeatable using the . repeat command.
yiw Yank inner word (copy word under cursor, say "first").
... Move the cursor to another word (say "second").
ciw<C-r>0 Change "second", replacing it with "first" ( is Ctrl-R).
... Move the cursor to another word (say "third").