How hard would it be to add an option in the settings to choose the location for the theme options link?
Perhaps a radio button for default administration areas to add a submenu with a drop-down list of each section (Dashboard, Appearance, Tools, etc)
A second radio button will allow a new menu to be created with a text input for the name of the new panel and maybe a dropdown for a display icon?
You could also create a folder for the icon as well. That would allow easily adding custom icons for the new menu (and perhaps the left menu in the actualy theme options!) And simply populate the dropdown with the list of icons in the folder.
The only issue I could see is if PHP isn't able to read the directory for whatever reason.