The easy variant will probably be to create a scheduled job that goes through the media items one by one and checks for references and then creates a report in an excel format or similar. Then you can run the job during off hours and don't need anything expensive search solution etc. If you are fine with a summary every day or so then this will likely be the easiest development route. It will likely take quite some time to run and put a bit of load on server during that time.

A more advanced version is to use EPiServer Find and add a custom field on each media to store whether it's used or not. Then you will need to build some custom logic to when content is published to check what references has disappeared or been added and update the index for those media items. When you got that information in index you can query that and get instant replies so if you need "live" results and performance then this is probably the way. It will not noticably put any load on server.