Two of these with seatbelts as the straps (best straps):
Wear them on both sides, on your hips, fasten them onto bikes as panniers, clip them together as one shoulder bag, or wear one as a backpack and one as a shoulder bag. They are tiny, so it requires you to pack light (which is a positive), and they make you look poor and unassuming but "vintage" enough to fit in with more bourgeois types. I keep each one weighing about five pounds, with only half its volume occupied with gear (the other half is for food). This means investing in ultralight backpacking gear, which is big money, but the payoff is worth it. This is what I'm taking to Europe.