You have two main options with a challenge like this.
1) Do it manually - While this option doesn't always sound like the most glamourous option, it's often a fairly reasonable step to consider during migrations. Writing and debugging advanced code that is only going to be used once can be costly, and there are plenty of people who specialize in data entry who are capable of helping out if you prepare a good workflow and take the time to train them on the task.
2) Do it programatically - If you take this approach, you'll probably be using an Extract, transform, load Process (also referred to as an ETL Process). In your case this would roughly equate to:
- Extract the data from your ExpressionEngine database
- Transform that data – processing the body and EE matrix haystack fields and updating the data into the format which you wish to import it into Craft
- Load your new data into Craft (using a script or import plugin like Brad mentioned in the above comments)
My firm runs a database migration service, The Great Migration, and I can confirm that it is possible to migrate ExpressionEngine sites using a "matrix image haystack" technique to Craft CMS. We have used both programmatic and manual steps in doing so for images, videos, and quotes using this technique. Your final solution will largely depend on the format and integrity of your source data and the desired format of your target data.