Taking an academic pseudonym?
Complementary to your own suggestions and the ones in the other answers, you could consider creating an ORCID (or of course any other unique researcher/author ID) and using it in all publications. The benefits here:


By adding a unique identifier to your name, the name collisions can be resolved. 
If your change your name at a certain point (e.g., if you decide to change your name as you suggested in the question), the ID will remain the same. Therefore, you even might be able to postpone the decision whether to change your name.
Since you mention online identity and SEO: At least ORCID comes with a profile web site (I am not familiar with other ID systems), where you can add your personal information and even maintain a list of your publications. Usually, a link to this profile is added to the publication, so readers can follow it. As to search engine optimization, I am not expert here but I would guess that the outcome of those algorithms improves if there is a unique ID that groups your contributions together.


Of course, all those ID systems are quite recent and might not be accepted (yet) by the journals and/or researchers in your field. Nevertheless, I would give it a try since it comes at no cost (which I presume won't be the case for changing legal documents).