If your function was strictly convex and $C^3$ (let's say on a compact interval $I$) and you had bounds on the third derivative there, it might be possible
to prove its convexity on $I$ by evaluating it at sufficiently many points of $I$.  If not, it's impossible to distinguish any convex function
from one whose second derivative has a narrow "blip" taking it below zero
between some of the points where you evaluated it.  

EDIT:
Here's what I had in mind.  Suppose you know that $|f'''| \le B$ on interval
$I$.  Evaluate $f$ at points $x_j = x_0 + j \delta$, $j = 0 \ldots n$ so that $I = [x_0, x_n]$, and compute $L_j = f(x_{j-1}) - 2 f(x_{j}) + f(x_{j+1})$, $j = 1 \ldots n-1$.  
Note that $L_j = \int_{x_{j-1}}^{x_{j+1}} (\delta - |t - x_j|) f''(t)\; dt$.
If $x_{j-1} \le s \le x_{j+1}$, since $f''(s) \ge f''(t) - B |t - s|$ we have
$$ \delta^2 f''(s) \ge L(j) - B \int_{x_{j-1}}^{x_{j+1}} (\delta - |t - x_j|)|t - s|\; dt
\ge L(j) -  B \delta^3$$
since
$$ \max_{s \in [-1,1]} \int_{-1}^1 (1 - |t|)|t-s|\; dt = 1$$
Thus if $L_j \ge B \delta^3$ for all $j = 1 \ldots n-1$ you can conclude that 
$f'' \ge 0$ and $f$ is convex. On the other hand, if some $L_j < 0$, $f$ is not convex.


If $f''$ is bounded away from $0$, 	this method is guaranteed to succeed
as long as $\delta$ is sufficiently small.  
 In fact if $f'' \ge c > 0$ on $I$, we will have
$L_j \ge c \delta^2$, so we just need $0 < \delta < c/B$.  Note that you don't need to
know $c$ beforehand, you just keep taking smaller and smaller $\delta$ until you succeed.