When I did research on the Communists in Brazil for my own timeline (in my sig below,) and when I took a class in second year dedicated to Brazil in the 20th century, I was never convinced that the Party (and others like them) would have taken over, bar a civil war between two other factions.
As you've pointed out, armed rebellion never got them anywhere; the forces that be were always far too strong. It didn't get them anywhere in the 1930s, in 1945 and 1951 when they started infiltrating rural cooperatives in Pernambuco to turn them into self-defence organisations, or in the 1960s-70s when they were fighting the post-'64 military government.
That said, they were nevertheless a force to be reckoned with up until the coup in 1964. The Communist Party of Brazil was outlawed in 1947 IIRC, but their members still managed to scatter themselves throughout the legal left-leaning parties and the trade union structure. Moreover, despite the illegality of the PCB, there wasn't as much of a stigma against Communists as, say, in the United States. This was very much the case in the disturbingly poor Northeast, which American journalists and aid workers in the early 1960s then misinterpreted as a hotbed of Marxist-Leninist intrigue. Yet this didn't stop destructive factionalism within the far-Left in Brazil, fuelled by the example of the Sino-Soviet split and the pettiness of individual leaders like Prestes and (AFAIK) Marighela.
I would say the Communists would have a chance at power by picking sides carefully in any Brazilian civil war. There were a few cases where this seemed possible - the 1964 coup is one - but then you'd have to look at cases outside Brazil to shape a plausible timeline, like the Spanish Civil War. The two chapters of my timeline where I stashed away more specific research are
here and
here. I examined the Communists in depth, so it might be useful.