Can quantum mechanics be formulated without any reference to pictures? NOTE: in the following with the word "picture" I refer to Schroedinger, Heisenberg, Interaction pictures, i.e. to the way the time-evolution is "distributed" between states and operators.
We often switch, according to what is more suitable to the problem under consideration, between various pictures (Schroedinger, Heisenberg, Interaction, various combinations of the above). This is purely, to my understanding, to ease formal manipolations, and the physical content of the theory is always independent of the picture used to describe it.
Is it possible to formulate quantum mechanics in a way that completely avoids the use of various pictures? The time evolution of the matrix elements
$$ \langle \alpha | \hat{O} | \beta \rangle (t)$$
is enough (is it?) to characterize the system at any time. Is it possible, at least in principle, to carry out calculations using just this and without any reference to pictures?
 A: As you say, pictures in QM are merely different ways to compute the exact same thing - the expectation value of observables $\mathcal{O}$. Now, in all pictures, we can derive Ehrenfest's theorem
$$ \frac{\mathrm{d}}{\mathrm{d}t}\langle \mathcal{O} \rangle = \frac{1}{\mathrm{i}\hbar}\langle [\mathcal{O},H]\rangle + \langle\frac{\partial}{\partial t}\mathcal{O}\rangle$$
which tells you how every expectation value evolves with time. It holds in all known pictures. In fact, it can be used to derive the Schrödinger equation. In this sense, it is an equivalent foundation of QM. As with all other ways of looking at QM, the fundamental insight here is that the Hamiltonian is the generators of time translations (just as it is in classical phase space mechanics, or the Koopman-von Neumann formulation of mechanics).
There's no more rigor to be found. All pictures are equivalent (for example, the Stone-von Neumann theorem shows Schrödinger and Heisenberg to be unitarily equivalent, essentially making the switch between them (as DanielSank comments) a basis change in Hilbert space) - you may start from the Schrödinger equation and say that time evolution operates on states, you may start from the Heisenberg time evolution and say that operators evolve, you may start from Ehrenfest's theorem. It's all the same.
