Is it possible to create taxonomies based on theme settings? That is, are theme settings actions run before taxonomies / post types are initialized?
Yes. Post types and taxonomies are (should be) registered on the
init hook. You are able to use
get_option inside that hook to retrieve your theme's settings and register your post type/taxonomy with args based on those settings.
(By the way post types and taxonomies are really plug-in territory... :) )