partial (and non deterministic) functions in dependently typed lambda calculus
It is possible to take a typed lambda calculus and add general recursion or fixed points. See for instance Plotkin's PCF, or HOFL in Winskel's formal semantics book.

In that way, one keeps the type system but introduces partiality. This is a very common approach for Turing complete typed programming languages.

Of course, now the logic associated to the calculus via Curry-Howard is no longer consistent, since every type is inhabited (by non terminating terms). This is not a serious problem for programming.

If wanted, in the type system one could distinguish between terms involving general recursion (which might not terminate), and terms involving no recursion or some known-to-be-terminating one, like (higher-order) primitive recursion. Note that this will not separate the programs between "halting" and "non-halting", which is undecidable, but only between "statically known to halt" and "statically unknown to halt -- they might or might not".

I have not thought much about that, but intuitively a non-termination monad would fit nicely in such type system. With a non-deterministic monad, one can also address non-deterministic functions.

A final comment: after reading the question, I am actually more concerned about the posted automaton-based example than termination. With dependent types, one can use the $\Pi$-type of a selection function (as the one which was posted), which given an automaton return one of the accepted strings (or a "empty-language" token). However, let's keep in mind that when a dependent type system checks a term against such $\Pi$-type, the term must contain the recipe to generate the string, as well as a proof that such string is accepted by the automaton. The posted question, in my view, seems to forget about that -- as if the type system could check any algorithm correct (in the sense of returning an accepted string). This is not possible.