Substitute images automatically across many pages

Hello,
I’ve just inherited a quite large wordpress site which has been developed by the business owner himself. The problem is that he has no competence at all in webdesign and the site has grown to a real mess:
– very bad html in pages
– no menu structure but all the (numerous) pages linked as in a wiki (which is creepy, I swear!) which makes difficult for me to give a sense to contents
– huge images, of childish quality, resized with html attributes
– all fonts customized locally, with no use of a style.css file
– text snippets copy/pasted many times all over the website to rehiterate a concept (and you know how google is fond of repeating text, right?!)

Well, I’ve already understood that most of my work will be in the editor, checking html page by page, creating a navigational structure, substituting in-tag styles with a stylesheet, but I’m dreaming to solve at least the images problems in an easy way. Part of my plan is to give to the site a professional look through substituting most of them with nice images.

Right now in WP the only way to substitute an image is to open the page/post, delete the old images and upload a new one. Yes, you could even do it at a html level, changing images url, but it could be even more frustrating…

So, I’m looking for a way to enter the media library, select an image in it and substitute all of its occurencies with a new image, automatically.

I can’t believe that there’s no mention on the web to the need to substitute images in big sites, and that no external plugin is available! Maybe I’ve looked in the wrong places!
Hope you have some idea to help.
Thanks very much for your help!!
Enrico