Ja, das Problem kenne ich auch nur zu gut. Zwar stammen geschätzt 98% meiner Apps aus dem freien App-Store F-Droid oder direkt der jeweiligen Herstellerseite. Aber manchmal fehlt eben doch die Alternative zu Apps aus dem Play Store.
In der Vergangenheit habe ich mir die Installationsdateien (.apk) über externe Downloadseiten heruntergeladen. Hier wird zum Beispiel auf Evozi verwiesen.
Titanium Backup und den MyPhoneExplorer Client habe ich mir wohl auch so besorgt, eine andere Downloadmöglichkeit fand ich auch nicht mehr.
Über F-Droid habe ich mir mittlerweile den Yalp Store heruntergeladen. Dieser bietet eine Suche im Google Play Store inklusive Download ohne Anmeldung.
Titanium Backup scheint Kontakte nicht sichern zu können, SMS in der Pro-Version dagegen schon (und Anruflisten sowie WLAN-Zugangsdaten). Der genaue Funktionsumfang im Vergleich.
Eine Alternative wäre neben dem von tphysm erwähnten SMS Backup+ noch Slight backup, wobei das Kontakt-Backup hier noch experimentell ist. Persönlich würde ich weiterhin MyPhoneExplorer favorisieren. Vielleicht ist ja der Yalp Store für dich ein gangbarer Weg?