Translation:We are looking for a parking lot near the theater.
"We are looking for A PARKING near the theater" would not normally be used. "We are looking for PARKING near the theater," on the other hand, certainly would be. But I will leave it up to the Czech natives on the team to decide whether that translation accurately reflects the Czech original.
According to the Cambridge Dictionary of English, "parking" is "the act of parking, or the spaces in which cars are parked" (https://dictionary.cambridge.org/dictionary/english/parking). I am not a native English speaker, but I use it for ~80% of my communication needs and, honestly, I haven't seen nor heard the expression "parking lot" in a long long time. It's either parking or carpark, with or without definite/indefinite articles.
Unless times have changed a lot, "parking lot" and "parking garage" are common in the US -- along with just "parking" -- while "carpark" is rare. But I digress.
I would expect an article to be used with everything other than just "parking." As in, "I'm looking for A/THE parking lot/parking garage/carpark near the (whatever)" -- but just "I'm looking for parking near the (whatever)."