It sounds very acceptable to me, the pleonastic phrasing in this case gives a slightly humorous tone, and stresses that this is just the very beginning of something. I would still refrain from using it in formal writing.

As you suggest, the other way round (“semblant de début”) is also acceptable.

You can even add more nouns to stress even further the idea that you are in the very modest and early stage of something:

“Cette enquête donne un semblant de début de chouia de réponse”

“J’ai senti un début de semblant de frémissement d’intérêt de sa part”