I created two plugins that together should solve my needs. They are currently in an early alpha stage, and all comments are welcome.
The base plugin is an On-Demand Resizer. This plugins monitors requests for non-existing files in the uploads dir, and creates images of the requested size if needed. For example, image-200x100.jpg will create and return image.jpg, but resized to 200 by 100 pixels. The image is saved by that name in the directory, so further requests are handled straight by the server.
The second plugin, Resize img tags, modifies <img> tags so their src attributes include width and/or height data. This allows the first plugin to serve the correct images. Together they do what I want, and I only need to create a run-once function to convert all existing posts, but that should be easy (I don’t want to hook into the_content for something that should run only once).
A third “bonus” plugin, Virtual intermediate images, intercepts the creation of the intermediate images when uploading a new image in WordPress. Since they are still created by the first plugin if requested, this allows you to specify multiple image sizes without taking up disk space unless they are actually used. This is not needed for the two first to work, but it was an easy addition, and it highlights the fact that I still need to work around the WordPress image editor, but I will do that when I create my thumbnail editor, which will also use the first plugin.