Are their problems that we can not even approximate efficiently?
Are there any natural problems for which this is not the case? 


Consider the scheduling jobs with deadlines on a single machine problem. I cannot say anything about its average time but this problem has no $\rho$-approximation unless $P=NP$. 

Suppose that there are $n$ jobs to be scheduled on a single machine, where the machine
processes at most one job at a time. Suppose also each job $J_i$ has 


release time $r_i  \geq 0$
deadline (due time) $d_i$


Define the delay by $D_i = t_i - d_i$ if the job $J_i$ finishes at $t_i$. So, we are interested in the minimization of the maximum delay, i.e.,

$$\text{minimize: } \max\{D_i\}, i=1,\dots,n$$

Now assume we have $\rho$-approximation algorithm for this problem. This means that our algorithm would find a solution which is not more than $\rho OPT$ (where $OPT$ is the optimal value). If for any problem instance with the optimal value equal to $0$ our approximation algorithm would find the solution at most $\rho 0 = 0$ in (polynomial time) and this would imply $P=NP$.