Find non-smooth function that meets conditions
As you mention, the function $f(n)$ needs to grow fast, though not necessarily exponentially fast ($n^{\log n}$ also works, for example). Nevertheless, let's take your suggestion $f(n) = 2^n$ for definiteness. Simplifying things a bit, you are looking for a function $T(n)$ such that


$T(n)$ is non-decreasing.
$T(2^k) = 2^{2^k}$.
$T(n)$ is not $O(2^n)$.


To satisfy the third condition, we would like $T(n)$ to be "as large as possible" given the first two conditions.


  (a) Find the function $T(n)$ which is "as large as possible" subject to the first two conditions.
  
  (b) Show that it satisfies the third condition as well.
  
  (c) For which functions $f(n)$ does this construction work?