Did the universe always have 4 space time dimensions? Is the dimensionality of spacetime in all usual models constant?
 A: Yes.
You've probably heard that string theory predicts the universe is 10 dimensional (and M-theory predicts it's 11 dimensional) while we only see 4 dimensions. However this isn't because the number of dimensions has changed, but because 6 (or 7) of the dimensions are rolled up into a very small circle.
having said this, there have been suggestions that the universe started out as 2 dimensional (1 space and 1 time) then the number of dimensions increased to 10/11/whatever as the universe evolved. However the idea comes from causal dynamical triangulation, and this is pretty speculative even by the standards of quantum garvity theories. There are even wilder suggestions that the spacetime dimension might be fractal.
A: In addition to what John Rennie said, meaning by the number of dimensions the universe has the number of large dimensions, there are (yep somewhat wild) suggestions how the number of these could change. (The total number of spacetime dimensions can not randomly be changed).
As explained in chapter 11 of The Shape of inner Space for example, if the vacuum describing our universe is not the global minimum in the string theory landscape, a phase transition to a lower vacuum energy state with other laws of nature, number of large dimensions, etc, could happen. Suggested mechanisms are some kind of a tunneling effect or thermal fluctuations. 
In such a catastrophic vacuum transition it is much more likely that the number of large unrolled dimensions would increase than decrease, since a large amount of potential energy is stored in the compactified extra dimensions which can be released in the process. 
