I wonder how to show the following:
Let $P_1,...,P_n$ be propositional symbols occurring in a tautology $\alpha$. Assume that $\varphi_1,...,\varphi_n$ are first order formulas and that $\alpha'$ is the result of substituting, for any $i$, the formula $\varphi_i$ for each occurence of the propositional symbol $P_i$ in $\alpha$. Show that $\alpha'$ is a valid formula.
My approach is to show that for every valuation $v \vDash \alpha$ and for every $i \leq n$ there is a first order structure $\mathcal{M}_v \vDash \alpha [P_i/\varphi_i]$ (is this a good argument?) Then I can just construct a structure based on $\varphi_i$ and leave the rest of $v$ unchanged for the other propositional symbols.
But I don't know what is the form of $\varphi_i$, so how can I construct a structure that models it? Should I reason case by case? Is this the best approach to solve this problem?
You probably want $\varphi_i$ to be sentences (or at least for them to have disjoint sets of free variables).
No, you're doing it backwards: you don't need to show that for every valuation you can find a structure which gives you the valuation. Indeed, it may not be possible for given $\varphi_i$ (say, when $\varphi_0=\forall x (x=x)$).
You need to go the other way around. Pick an arbitrary model $M$. This gives you a valuation $v$. Then apply whatever definition of truth in a model you are using, along with the fact that $\alpha$ is a tautology, to show that $M\models \alpha'$. (You may need the following lemma: if $\alpha$ is a propositional formula, $v$ is a valuation such that $v(P_i)$ is true if and only if $M\models \varphi_i$ for some sentences $\varphi_i$, then $M\models \alpha'$ if and only if $v\models \alpha$. This should be straightforward induction with respect to the complexity of $\alpha$.)
Reasoning case-by-case might be a little hard. After all, there would be infinitely many cases to consider.