When trying to freeze python (2.7) application with any of cx_freeze, bbfreeze, pyinstaller or py2exe, the frozen application cannot find google.protobuf.
In logs of the freezing process there is usually something like 'cannot find google'. So the google package is not found and not packaged, although it's in python's site-packages and the non-frozen version works just fine.
I've already had a solution when writing the question - I'm putting it here because it's probable that other people will find it here easily.
The solution: Create empty __init__.py in Lib/site-packages/google of your python installation directory, and compile it somehow (import google in interactive python session for example).
When there is __init__.pyc in the package directory, the freezing tools start to work.