There are a lot of free icon sets under the GPL you could use. Considering the amount of work put into making life easy in the creation process it would be good to have a dropdown list of images to assign the new Header (or some other easy to use feature).
For testing purposes you could simply add a dropdown with a generic directory "icons" and a made-up path to an image. Run a simple for(i=...) to populate it with a random number for the list and update the database with the selection.
Assuming the basic test is easily down and assured you can then create a base array of 15-20 icons to put in the folder and create a path to.
//icons are the standard 20px*20px size
$icon_arr = array("tools.png", "questionmark.png", ...)
$dir = ABSPATH . 'wp-content/plugins/plugin-folder/icons/img.gif'
To make life easy for others to change the items I would create a seperate php file and/or class so that anyone can add/change/remove the icons. Especially if they have their own custom icons.
I hope that all made sense.
Also, you'll likely want the xHTML hardcoded instead of relying on a stylesheet to limit issues when people change icons.
<img src="" style="float:right;">