They recently introduced metafields per variant.
So you could introduce a variant metafield under Settings > Metafields:
Which shows up on the variant editor like this:
You might have this setup:
|Product||Product Title||Product SEO Title||Variant Title||Variant SEO Title [Custom Metafield]|
|A||Accent Tub Chair||Accent Tub Chair||Black PU Leather||Black Faux Leather Tub Chair|
|A||Accent Tub Chair||Accent Tub Chair||Beige Tartan Fabric||Beige Tartan Fabric Tub Chair|
From there it would be pretty straightforward to combine fields + some SEO title liquid logic something like: IF Variant SEO Title is not blank, THEN use it, else fallback to Product SEO Title + Variant Title.
But you've also got the problem of sitemaps (variants not in it), canonicals (would need to switch to self-canonicalized to get indexed), and then also you probably want to have some LINKS between variants to ensure there is a crawl/click path to them.
So it's all possible, there are just a few things to consider. Another approach is to break them out into separate products and create custom variant selectors on the product page for defined "product groups".
I would suggest that if you're intending to do this for SEO reasons, start with keyword research and work your way out from there to help pick a SEO title convention and then after that, how that can be implemented by theme and/or metafield customization.