Para responder à parte específica da sua pergunta:
Can I run any natively compiled code, as long as it is compatible with the hardware architecture?
Sim, você pode. No entanto, você pode fazer isso mesmo sem raiz - desde que seja um APK . Um APK pode conter código compilado nativamente e pode ser instalado sem acesso root. Para criar um APK com código nativo, você pode usar o "Kit de desenvolvimento nativo" (NDK) , que é gratuito para download.
Naturalmente, o código nativamente compilado não terá permissão para fazer certas coisas (como excluir o sistema operacional) se ele não estiver sendo executado como root. Se estiver rodando como root, o código será capaz de fazer praticamente tudo, assim como em outros sistemas operacionais, como Linux ou Windows.
Para obter mais informações sobre o código nativo no Android, veja também esta pergunta: limitações do Android NDK