This summer I tried to rent a car in Warsaw without a credit card. It wasn't an easy task and it took my hours of talking until I could convince them that it is possible. However, I had to pay the whole bail money in cash.
For the next time, I would like to ensure if there is a company in Poland that does not require a credit card for renting a car.
Last time I used Budget.