most of those cities you named have a covered market. either in the market or ajacent the market you will fine bottled water, bread and sandwich making supplies that are much superior to the usa.

to find covered markets, get a micheline red guide(italy for instance) and find the covered market symbol. you can usually get michelins out of your library. age makes no difference, as the markets seldom move(the one in bruges is closing in on 1000 years old).

in venice, the going price for bottled water is €0.85 per 1-1.5L bottle. bring your own bags or buy one. a very cheap nylon backpack is great for water if you are buying 4 or 6 bottles at once.

you can ask at any front desk, (ask for cheese if you don't want to ask for water).