Perhaps when the Brazilian economy goes down the drain in 1929/30, no one rises to take the reins of the country? Arguably, Vargas was what Brazil needed at the time. So the República Velha goes on, presiding over Brazil's decline in the 30's and 40's. Question is: What comes later to ensure the desired outcome?
This is a very good option indeed. But I think that you need to go earlier than 1929. Without Vargas probably some representative of the Tenentistas would take power later (and my bet is that he would still be from Rio Grande do Sul, because in the 1920's the Southerners were maybe the most interested in breaking the political system of the Old Republic).
I would propose an earlier POD with an even more federalised Old Republic, where the governors and mayors have even more power than IOTL, and in some point they just do not obbey anymore the federal government. For example, it would be an Old Republic where the Contestado War really happens as an armed conflict between Santa Catarina and Paraná, without any intervention of the federal government (almost as the 1923 Revolution in Rio Grande do Sul, where the federal intervention was minimal).
Other idea that could help is to slow or stop the industrialization. São Paulo would still hold the main economical position due to the coffee exports, but if the crisis of 1929 still happens and there is no national industry to take the place of coffee as the main economical activity there then the paulistas would have less power within the federation, creating political instability.
Finally, we could have more "cangaceiros" creating a kind of personal 'fiefdoms" within the states of Northeast, and maybe some similar kind of armed groups of popular bandids acting more successfully in other regions.