Can the fundamental theorem of calculus be proved without an appeal to mean value or Rolle's theorem or its immediate consequences? I think the answer is in the negative. Here are two of the ways I know. Both of them use
the Mean Value Theorem. The first one use in an indirect way, and the second uses
it more forthrightly. The first proof goes something like this.
Prove that $F(x) = \int_a^x f(t) dt, a \le x \le b$ is a particular anti derivative and if $G$ is an anti derivative that is $G^\prime =(x) = f(x)$. Then apply the Mean Value Theorem to $F-G$ on any interval $(c,d) \subset (a,b)$ to conclude that $F(c) - G(d) = 0$. Now keep $c$ fixed and move $d$ in the interval
$[a, b]$. Use $F(b) - G(b) = F(a)-G(a)$ to conclude $G(b) - G(a) = F(b) - F(a) = F(b) = \int_a^b f(x)dx$.
The second proof, which I prefer, goes something like this:
$G(b) - G(a) = \int dG = (G(b) - G(x_{n-1})) + (G(x_{n-1}-G(x_{n-2}) )+ \ldots (G(x_1) - G(a))$ for any partition $\{a, x_1, x_2,\ldots, x_{n-1}, b \}$ of $[a, b] $. Now
you use the Mean Value Theorem to write replace each term $G(x_k) - G(x_{k-1})$
by $G^\prime(c_k)(x_k - x_{k-1})$ to get a Riemann sum which converges to $\int_a^b f(x)dx $.
I think one has to use some sort of theorem like mvt which gives you global information $f(b) - f(a)$ of $f$ using the derivative which can only provide local information on $f$. 
 A: As others have said, in the version of FTC in which we agree to integrate / antidifferentiate only continuous functions, the only place where a consequence of MVT occurs is when we want to assert the uniqueness of the antiderivative up to a constant, which -- as N.S. points out -- is equivalent to the Zero Velocity Theorem (ZVT):
Let $f: [a,b] \rightarrow \mathbb{R}$ be differentiable with $f'$ identically equal to zero.  Then $f(x) = f(a)$ for all $x \in [a,b]$.
It is traditional to prove ZVT by noting that its contrapositive form is that a nonconstant differentiable function has a point at which the derivative is not equal to zero, and that this follows immediately from MVT.  This is the way I proved ZVT in my recently completed Spivak Calculus class.  Just for fun though, let me give an alternate proof using Real Induction (see e.g. page 14 of
these course notes).
Note that it is no loss of generality to assume that $f(a) = 0$ and show that $f$ is identically zero on $[a,b]$.  For $\epsilon > 0$, let $S(\epsilon)$ be the set of $x$ in $[a,b]$ such that for all $y \in [a,x]$, $|f(y)| \leq (x-a)\epsilon$.  If we can show that $b \in S(\epsilon)$ for all $\epsilon > 0$, then we have that $|f(y)| \leq (b-a)\epsilon$ for all $y \in [a,b]$ for all $\epsilon > 0$, so $f \equiv 0$.  Now:
(RI1) Since $f(a) = 0$, $a \in S(\epsilon)$.
(RI2) Suppose that for some $a \leq x < b$, $x \in S(\epsilon)$.  Since $f'(x) = 0$, there exists $\delta > 0$ such that $|y-x| \leq \delta$ implies $|f(y)-f(x)| \leq  
\epsilon |y-x| \leq \epsilon \delta$.  Thus for all $0 < \delta' \leq \delta$ and $y \in [x,x+\delta']$,
$|f(y)| \leq |f(x)| + |f(y) - f(x)| \leq |f(x)| + \epsilon \delta' \leq (x-a)\epsilon + \delta' \epsilon = (x+\delta'-a)\epsilon$,
so $[x,x+\delta] \subset S(\epsilon)$.
(RI3): Similarly, suppose $a < x \leq b$ and $[a,x) \in S(\epsilon)$.  Choose $\delta > 0$ such that $|y-x| \leq \delta$ implies $|f(y) - f(x)| \leq \epsilon |y-x| \leq \ \delta \epsilon$.  For $y \in [x-\delta,x]$, we have
$|f(y)| \leq |f(y) - f(x-\delta)| + |f(x-\delta)| \leq \delta \epsilon + 
(x-\delta-a)\epsilon = (x-a) \epsilon$.
I can't think of a situation in which I would rather give this proof than prove the Extreme Value Theorem and use that to to prove the Mean Value Theorem, but I find arguments by real induction to have a certain charming directness to them...
A: I think of the FTC as a sharpening of the MVT, so it would seem artificial to me to prove the FTC without the MVT.
Consider: The MVT states that, when $f(x)$ is continuous on $[a,b]$ and differentiable on $(a,b)$, then there exists $c\in (a,b)$ such that the slope of the tangent line to the graph of $f(x)$ at $c$ is precisely equal to the slope of the line passing through $(a,f(a))$ and $(b,f(b))$. We don't know anything about the point c.
Wait a second! We do know something about c! We know that $f^{\prime}(c)$ is the average of the derivative between $a$ and $b$! How do we know this? Well, if the function were linear, the average would just be the slope itself; and now that it isn't linear, well, the average is still the slope of the aforementioned line. Think about it- the derivative is velocity. Sometimes the car goes faster and sometimes it goes slower, but its average velocity will be the velocity $v$ such that, if it were traveling at constant velocity $v$ all the time, it would get from $f(a)$ to $f(b)$ in time $b-a$.
Now we want a way to write down that $f^{\prime}(c)$ is this average. How do we do it? Well, the average is the total divided by the number of parts, each weighted by its length. Wait a second- the numerator of that is the Riemann integral! Taking limits, the average of $f^{\prime}$ on $(a,b)$ is $\frac{\int_{a}^b f^{\prime}(t)dt}{b-a}$. So we've rewritten the "average version" MVT as $\frac{f(b)-f(a)}{b-a}= \frac{\int_{a}^b f^{\prime}(t)dt}{b-a}$. Multiply both sizes by $b-a$ and you're finished.
To turn this into honest mathematics you use some kind of formal argument like you mentioned- but morally, there's nothing more to the FTC than the interpretation of $f^{\prime}(c)$ as not just $f^{\prime}$ evaluated at some strange point, but rather as an average.
Added: Because other answers are saying yes, I should stress that I'm saying no. There's an irreducible difficulty to the FTC, which is to translate between an epsilon-delta concept $\int_a^b f^{\prime}(t) dt$ and a number $f(b)-f(a)$. You have to cross that bridge somehow. And the only ways across are the IVT and the EVT, which in this context come in the guise of the MVT. I wish I had a logician to comment- but I think that, logically, I'm going to go out on a line here and assert that there can be no way to the FTC which doesn't pass through some form of the MVT.
Added 2: There are a number of different ways to formulate completeness of the real numbers. As other Pete L. Clark's and N.S.'s answers have shown, these, and techniques such as real induction, can be leveraged to yield genuinely different proofs of the FTC. So the answer turned out to be yes after all! 
A: For an alternative approach to the FTC without the MVT, see this paper, which also contains other references:

Tucker, Thomas W.; Rethinking rigor in calculus: the role of the mean
  value theorem.  Amer. Math. Monthly 104 (1997), no. 3, 231–240.
  http://dx.doi.org/10.2307/2974788; also available at http://www.math.cornell.edu/~maria/1220/ .

This article has brought a reaction:

Swann, Howard;
  Commentary on rethinking rigor in calculus: the role of the mean value theorem. 
  Amer. Math. Monthly 104 (1997), no. 3, 241–245. http://dx.doi.org/10.2307/2974789; also available at the author's site: http://www.math.sjsu.edu/~swann/commall.pdf.

and also this

Scott E. Brodie; On "Rethinking Rigor in Calculus...," or Why We Don't Do Calculus on the Rational Numbers. The College Mathematics Journal , Vol. 30, No. 2 (Mar., 1999), pp. 135-138. http://www.jstor.org/stable/2687725.

A: If $f$ is defined on $[a,b)$ such that $F(x)=\int_a^x f(t)dt$ exists for all $x\in(a,b)$, and $f$ is continuous at $x_0\in (a,b)$, then, given $\epsilon>0$, find $\delta>0$ such that $I=(x_0-\delta,x_0+\delta)\subset (a,b)$ and $|f(x)-f(x_0)|<\epsilon$ when $x\in I$.
Then we can see that, for $0<h<\frac{\delta}2$, that $F(x_0+h)-F(x_0) = \int_{x_0}^{x_0+h} f(x)dx$ and 
$$f(x_0)-\epsilon < f(x) < f(x_0)+\epsilon$$ on the interval $[x_0,x_0+h]$.  So 
$$hf(x_0) - h\epsilon \leq F(x_0+x) - F(x_0) = \int_{x_0}^{x_0+h} f(x) \leq hf(x_0)+h\epsilon$$.
Divide by $h$ and you get:
$$f(x_0)-\epsilon < \frac{F(x_0+h)-F(x_0)}h < f(x_0)+\epsilon$$
So $\frac{F(x_0+h)-F(x_0)}h$ has the limit of $f(x_0)$ as $h\rightarrow 0+$.
You can show the same for $h\rightarrow 0-$, so you are done.
Note, you need continuity at $x_0$ for this to work, since, if you define $f(x)=-1$ for $x<0$ and $f(x)=1$ for $x\geq 0$, then the integral of $f$ is not differentiable at $x=0$.
So, all you really need is that the following theorems:
If $u<f(x)<v$ for all $x\in[x_1,x_2]$ then $(x_2-x_1)u\leq \int_{x_1}^{x_2}f(x) dx \leq (x_2-x_1)v$.
A: You can prove that $F(x) =\int_a^x f(t) dt $ is an antiderivative of $f$ without Rolle or MVT.
Then, you need MVT to prove the following result: if $H'=0$ on an interval, then $H$ is constant. 
I think you can prove this result without MVT. I will prove it for any close interval $I$, if your interval is open, you can get it by looking to any closed subinterval.
Fix $\epsilon >0$. Then for each $x \in I$, there exists some $\delta_x$ so that 
$$|x-y|< \delta_x $$ implies $|H(x)-H(y)| < \epsilon |x-y| $
Now $\cup (x-\delta_x, x+\delta_x)$ is an open cover for $I$, thus you can find a finite subcover.
Let $a < b$ be in $I$. Pick $x_0=a, x_1,..,x_n=b$ some increasing sequence so that $x_i, x_{i+1}$ are in the same intervals. This can be done since the subcover is finite...  (See the details at the end of the proof)
Then 
$$|H(a)-H(b)| = |\sum H(x_{i+1})-H(x_i)| < \epsilon(b-a) \,.$$
The rest is simple.
Edited Here is how you can prove the existence of $x_n$.
Let $I_1,.., I_k$ be the finite open cover, with $I_k= (c_k,d_k )$.
$x_0=a$. This is in some interval $I_{k_0}=(c_{k_0}, d_{k_0})$. 
If $b \in I_{k_0}$ then we are done. Otherwise, $d_{k_0} \leq b$.
$d_{k_0} \in I$, means $d_{k_0} \in some I_{k_1}$. Since $I_{k_1}$ is open and contains the end point of $I_{k_0}$, we have $I_{k_0} \cap I_{k_1} \neq \emptyset$.
Pick some $x_1 \in I_{k_0} \cap I_{k_1}$.
Repeat the process, picking at each step some $x_i \in I_{k_i} \cap I_{k_{i-1}}$ so that $x_i$ is at the right at $I_{k_{i-2}}$.
This can be done since $d_{k_{i-2}} < d_{k_{i-1}} $ and $ d_{k_{i-1}}$ is an interiour point in $I_{k_i}$. Thus, $\max( d_{k_{i-2}}, c_{k_i}, c_{k_{i-1}} ) <   d_{k_{i-1}}$ and all you need is to pick some $x_i$ in between.
Once you pick a point in an interval, tyou'll leave that interval in at most two steps and never get back... And the process can only end when $b$ is in some $I_{k_n}$, but needs to end in finitely many steps....
A: "Can it be proved..." 
Yes, strictly speaking. One could go to the extremes - one can prove the Lebesgue Differentiation Theorem, which I would not at all call an immediate corollary of the MVT. Nor does one need the MVT to prove it at all. For example, see here.
Really though, all we need is a bound. We use the MVT because it's pretty good, but just knowing that the value of a function is bounded above and below on an interval, then it's integral is bounded above and below by the max and min times the length of the integral.
Any sort of average will work, really. But these are all more or less equivalent, so it's not so exciting.
