From what you describe these ads are separate pieces of information which you want to order and display based on their properties. That would mean storing them as custom posts is still the way to go. After all, posts are the way WordPress stores chunks of related information. That doesn’t mean they have to be displayed separately. Menus are also stored as a post type, even if they are only included in templates that also include regular posts, and are handled in a completely different way.
Now you have the separate ads in a post type, you can use wp_query to select them and display them in a template. Roughly, there are two ways to go. If you control the template, you can create widget areas in appropriate places and write a widget that displays the ads. If you don’t control the template you can write a shortcode and include it in regular posts/pages.
You would assemble all code (custom post type and widget/shortcode) in a plugin. The benefit of doing it this way would be flexibility for future developments. You could, for instance, place individual ads on content pages, if you would choose to do so.