I've been using Dr Scholl ballet flats for travelling, they come with removable and washable memory foam insoles. Comfortable enough for mild hiking even. I imagine this brand would have something similar for men.