Your question is about many things, but let me give an answer focused on just one interesting issue, the question of determining how long a program will run.
The busy beaver
function exactly measures how long programs of a given size
run before halting (among the ones that do halt). There are
versions of the busy beaver function for any notion of
computation, but let us consider the case of C programs,
since you mentioned them. Note that for any natural number
$n$, there are an enormous number of C programs of size
$n$, measured in kilobytes, say. Nevertheless, this
enormous number is finite. Among all programs of size at
most $n$, some halt and some do not. Define $b(n)$ to be
the running time in clock cycles of the longest-running but
halting C program of size at most $n$.
The interesting thing is that the busy beaver function is
not computable! If we had a way of computing $b$, then we
would be able to solve the halting problem, since given any
C program, we look at its size $n$, compute $b(n)$ and run
the program for that many steps; it it hasn't halted by
then, we know it will never halt. Another way to say this
is that if we have an oracle black-box that allows us
somehow to compute the function $b$, then we would be able
to answer any halting problem query. Since it is impossible
to solve the halting problem, it follows that we cannot
compute the busy beaver function.
Edit. In your update, you mention the problem of solving the halting problem 99.99% of the time. The general problem of solving almost all instances of a problem, as opposed to all instances of a problem, gives rise to the subject known as generic case complexity. In particular, the black-hole phenomenon occurs when the difficulty of an unsolvable or infeasible problem is concentrated in a very tiny region, outside of which it is easy. It is not good, for example, to base an encryption scheme on a problem whose difficulty has high worst-case complexity, but whose average-case complexitty is low, for if the robbers can rob the bank 10% of the time, it is good enough for them.
In fact, Alexei Miasnikov and I proved that the halting problem itself admits a black hole---for some of the standard computation models, there is a method to solve the halting problem with probability $1$, using the natural asymptotic density measure on the space of programs. I explain further details in this MO answer.
As far as I know, the answer is no. We don't have an argument not based (directly or indirectly) on digonalization for even proving there is a language outside Dec (The set of Turing decidable languages).
Characterizing a class means having criteria for showing when a language is in the class and when a language is not. The second part would give us tools to prove lowerbounds on such classes.
For very small classes like $AC^0$ and $AC^0[p]$ there are combinatorial arguments (also for monotone-$AC^0$ circuits), but the current state of knowledge is consistent with $AC^0[6] = NP$. The Razbarov-Rudich (RR) Natural Proofs theorem is related to why the previous combinatorial arguments haven't been successful in separating larger classes. In simple terms, there is no "natural proof" for separating the larger classes unless there is no pseudo-random number generators (many believe they do exists), and all previous proofs were natural. Tim Gowers wrote a number of interesting blog posts on the topic:
http://gowers.wordpress.com/2009/09/22/a-conversation-about-complexity-lower-bounds/
The reason that we have pumping lemmas for $Reg$ (regular languages) and $CFL$ (context-free languages) is that the machine models for them are very specific which gives the strings accepted by them special combinatorial structure. For classes defined by Turing machines this is not the case. If a complexity class contains some basic functions (say $AC^0$) and is closed under composition, proving lowerbounds for it becomes a rather difficult task. Note that $Reg$ does not contain $AC^0$ ($\{0^n1^n: n \in \omega \}$ is in $AC^0$ but not in $Reg$.)
EDIT:Comments
part 1.
I don't have a theoretical justification right now, but the history of complexity theory shows that the structure of much smaller complexity classes are at least very difficult to understand. Many experts "believe" that there are pseudo-random number generators (PRNG), so RR's Natural Proof theorem applies and there is no "natural" property of sets/functions that can be used to prove a lowerbound for the complexity classes satisfying the condition of the RR theorem. I think a person accepting the existing of PRNGs can at least claim that there are no simple combinatorial structures for these complexity classes.
part 2. You are looking for a combinatorial property of sets of strings in a complexity class. The computational complexity of checking a property is a good measure. Any property stated in the first order logic (on a finite structure) is $AC^0$. The RR theorem applies to properties which are in $P$, i.e. can be checked in polynomial time given the truth table of the functions (characteristic functions of sets restricted to inputs of size n). Encoding Turing Machines (TM) is not difficult, and I think it can be done if one goes a little above $AC^0$, e.g. $TC^0$ is probably capable of checking if a string encodes a TM. You are looking for a property that holds for all functions in a class, but not for those outside it. The negation of it would be a property of the kind considered in RR's theorem. By these considerations, I think there are no properties of the kind you are looking for unless there are no PRNGs.
definitions:
$AC^0$ is class of sets of strings accepted by (uniform) circuits of polynomial size and bounded depth, i.e. there is a constant $d$ and a polynomial $p(n)$ and a sequence of circuits $\{C_n\}_{n \in \omega}$ using unbounded fan-in $\land$,$\lor$,$\lnot$ gates and of depth $d$ and size $p(n)$ that accepts them.
$AC^0[n]$ is the same as $AC^0$ but allows $mod_n$ gates. $p$ is a prime number.
$TC^0$ is the same as $AC^0$ but allows majority/threshold gates.
A property $Q$ is natural if it is:
useful: i.e. does not hold for simple functions (functions of low complexity) but holds for some function in the larger class,
constructive: i.e. can be checked in polytime from the truth table of the functions,
large: i.e. for some k and all large enough n, the property holds for at least $\frac{1}{n^k}$ of the functions.
Best Answer
Joel Hamkins points out that the decision procedure for any reasonable notion of "computability" is not going to be solvable by a function that is "computable" within that notion.
Here is a contrasting example of a nontrivial model of computation in which the halting problem is solvable in the usual sense of computation. An index $e$ in our new system is a pair $(e_1, p)$ where $e_1$ is an index for a Turing machine and $p$ is a code for a polynomial over $\mathbb{N}$. In our new system, program $e$ is said to compute output $o$ on input $n$ (write $P_e(n) = o$) if and only if Turing machine $e_1$ computes $o$ on input $n$ in less than $p(|n|)$ steps. If $e_1$ runs for more then $p(|n|)$ steps then we say the computation of $P_e(n)$ is undefined (i.e. does not halt). Here we assume the Turing machine uses binary coding for numbers and we let $|n|$ be the number of bits required to express $n$ in binary notation.
This restricted model of computation is relatively common in the study of polynomial-time computability, where an index of the form $e = (e_1, p)$ is called a "polynomially clocked Turing machine". It's immediate from the definitions that a function is computable in the restricted model if and only if it is computable in polynomial time. Thus the model includes a very wide class of functions. However, because the time bound for index $e$ is already included in $e$, we can solve the halting problem for this model of computation with a normal Turing machine. (We cannot solve it with any polynomially clocked machine, of course.)