Can we always make a strictly functorial choice of pullbacks/re-indexing?
No, it is not always possible to make a strictly functorial choice of pullbacks. Four years later, I found a simple (if contrived) counterexample for this:
Let $\newcommand{\C}{\textbf{C}}\C$ be any full subcategory of $\textbf{FinSet}$ containing infinitely many sets of size 2, and at least one set of every finite size, but only one set of size 4. Certainly $\C$ has all pullbacks, since it is equivalent to $\textbf{FinSet}$.
Now pick specific 1- and 2-element sets $\newcommand{\one}{{1}}\newcommand{\two}{{2}}\one$, $\two$. Let $r : \two \to \one$ be the unique possible map, and $s : \one \to \two$ either of the two possible such maps. Then $s$, $r$ form a section-rectraction pair $\one \to \two \to \one$, with $rs = \newcommand{\id}{\mathrm{id}}\id_\one$.
If $\C$ had a strictly functorial choice of pullback functors, then the functors $r^* : \C/\one \to \C/\two$ and $s^* : \C/\two \to \C/\one$ would also be a (strict) section-retraction pair, with $s^* r^* = \id_{\C/\one}$. In particular, this would exhibit the subcategory of $\C/\one$ on 2-element sets (which is infinite) as a strict retract of the subcategory of $\C/\two$ on “maps into $\two$ where each fiber has size 2”, which has only 3 objects since $\C$ had only one object of size 4. But this is impossible: a finite category can’t be a strict retract of an infinite one.
Many years ago, Peter Freyd published (I think he published it) a paper in which he showed that while it was possible to replace any category with products by a category with canonical products, the same could not be done for pullbacks. The only thing I remember about the paper was the use of the word "table" for some construction. If you can't find it, write to Peter directly.
Here's an argument (assuming global choice) that the codomain fibration will always be split in "natural" cases. Perhaps it's well-known, or perhaps it has an important shortcoming (such as the use of choice?). Or perhaps there's an error -- strictification is tricky!
Claim: Let $C$, $D$ be categories with pullbacks, and suppose there is a functor $p: C \to D$ with the following properties:
$p$ preserves pullbacks.
$p$ is an isofibration, and induces an isofibration on all slices (perhaps this is redundant?).
$p$ reflects identities (i.e. if $f: c \to c$ is an endomorphism in $C$, and $pf: pc \to pc$ is an identity, then so is $f$).
There is a cardinal $\kappa$ such that for every $f: x \to c \in C^{[1]}$, the isomorphism class $[f]$ of $f$ in the fiber category $p^{-1}(pf) \subseteq C/c$ has cardinality $\kappa$.
The claim is that if $D$ admits strict reindexing, then so does $C$, and $p$ preserves the strict reindexing.
Upshot: Most "natural" categories $C$ admit such a functor $p: C \to \mathsf{Set}$, with $\kappa$ being the cardinality of the universe (perhaps with an exception for objects over $\emptyset$, which often doesn't matter because there are few maps into $\emptyset$). I'm assuming that $\mathsf{Set}$ admits strict reindexing (right?). So most "natural" categories do as well.
EDIT: $\mathsf{Set}$ does indeed admit strict reindexing. To see this, as in the comment below, note that the fibration $\mathsf{Set}^{(-)} \to \mathsf{Set}$ admits a splitting, and the fibration $\mathsf{Set}/(-) \to \mathsf{Set}$ is isomorphic as a fibered caegory -- the fact that it's equivalent as a fibered category is standard, and each isomorphism class in each fiber category has the cardinality of the universe, in both fibrations, so an isomorphism of fibrations exists. So $\mathsf{Set}/(-) \to \mathsf{Set}$ also admits a splitting as desired.
So indeed, most "natural" categories admit a strict reindexing. Of course, it's completely undecideable to compute it because the choice function must solve the isomorphism problem!
Proof of Claim: Let $()^\ast$ be a system of strict reindexing in $D$. Fix enumerations of the isomorphism classes of the fibers of $p$ by $\kappa$ (using condition (4) and choice). Now, if $\gamma : c' \to c$ is a morphism in $C$ and $f: x \to c \in C/c$, take an arbitrary pullback of $f$ along $\gamma$. Because $p$ is an isofibration (condition (2))and $p$ preserves pullbacks (condition (1)), we can correct this choice to lie over the canonical pullback $(p\gamma)^\ast(pf)$. Moreover, we can choose a representative which has the same index under our enumeration as $f$ does; let's call it $\gamma^\ast(f)$. It remains only to nail down the lift of the other leg of the pullback square, but any two choices differ by an automorphism of $\gamma^\ast(f)$ which lies over the identity on $(p\gamma)^\ast(pf)$, so by condition (3) this choice is uniquely determined.
It's now obvious that the lifted operation $()^\ast$ is strictly functorial, because it preserves the indexing by our enumerations.