Lo usual, si quieres escribir programas para android es hacerlo en Java (o Kotlin). Lo que estarías programando en ese caso sería una aplicación como tal. Y probablemente eso es lo que querías preguntar.
Ahora, para entrar en el tema de Linux como tal, sí se pueden compilar programas para correrlos directamente en Android (sin interfaz gráfica, o sea, solo por línea de comandos). Usualmente necesitas un toolchain con el que puedas compilar para la arquitectura arm (usualmente C, C++, pero seguro también se puede en rust y otros lenguajes), y luego asegurarte de enlazar estáticamente las dependencias de tu programa, y luego correrlosd desde la línea de comandos (bien sea desde un "adb shell" o usando Termux), pero en general es muy tedioso. Esto solo es recomendado si sabes lo que estás haciendo y no lo puedes hacer con una aplicación de Android.
Ahora, para entrar en el tema de Linux como tal, sí se pueden compilar programas para correrlos directamente en Android (sin interfaz gráfica, o sea, solo por línea de comandos). Usualmente necesitas un toolchain con el que puedas compilar para la arquitectura arm (usualmente C, C++, pero seguro también se puede en rust y otros lenguajes), y luego asegurarte de enlazar estáticamente las dependencias de tu programa, y luego correrlosd desde la línea de comandos (bien sea desde un "adb shell" o usando Termux), pero en general es muy tedioso. Esto solo es recomendado si sabes lo que estás haciendo y no lo puedes hacer con una aplicación de Android.