É possível construir um SO smartphone como o Android do zero (sem usar o código fonte deles), por você mesmo? Quão difícil seria?

Literalmente do zero seria um trabalho duro agora. Smartphones quase todos rodam uma variante dos sistemas operacionais existentes: iOS do OS X codebase, Android do codebase Linux e Windows do codebase Windows (esta é uma simplificação, é claro). Então você precisaria começar escrevendo um kernel, depois as ferramentas em cima dele incluindo a interação com módulos de rádio, que é o bit coberto pelos regulamentos, e depois uma GUI. A seu favor, os componentes estão mais ou menos padronizados agora, assim a camada de hardware não seria tão ruim embora você possa ter que comprometer com blobs binários para o hardware de rádio novamente.

Como ilustrações, um dos problemas do Ubuntu Touch era que ele ainda tinha que confiar nos drivers do Android para vários componentes, então ele estava efetivamente limitado aos telefones que suportavam AOSP.

Purismo estão atualmente tentando construir um telefone que roda puramente em Linux, e eles estão se concentrando em uma única plataforma, as CPUs i.MX 6 e 8, e eles estão trabalhando com desktops existentes, GNOME 3 e KDE Plasma Phone.

Em suma, não impossível se você escolher um ponto de partida bem documentado, mas muito trabalho.