I cannot find the "Change the Look" option in a My Site site. Is theming possible in a My Site Host web application?
You can change the "Look and Feel" for My Site using the URL:
Its the same URL as defined in "Change the look" section of Site Settings.
Yes it is possible, but not using the SharePoint default features, you have to use a theme that include specific master pages for those sites.
I don't know what is the version that you are referring to but I'm attaching two examples from 2010 and 2013.