I don't use these exe converters, but I'm assuming it isn't packing the image file in the executable, in this case you have to take a look on the manual and see if there's a way to force that file manually (or tell us what exe packer you're using).
You can of course, embed the image in the source file itself, I recommend using base64 for that (http://docs.python.org/2/library/base64.html). You can 'embed' any data in the code using it. Considering that an application icon is generally a PNG of few bytes, it's not a bad idea imho.
However, I don't recommend using an exe converter (and packing everything in a single exe), I suggest you use a 'fancy installer' and try reproducing the "clients" environments (in terms of dependencies) as consistently as possible... So you ship a single exe that 'unpacks' the entire structure, including dependencies, so in case you release an update, the download is probably going to be minimal (probably you won't need to update the interpreter and libs often).
If you don't want to ship the 'py' files (although in some way you're always shipping them (at least the 'pycs')), there are exe packers that creates separated files. Best Regards.