The idea of adventure without violence is something which may seem a bit of an oxymoron in RPGs but which in story writing is far less difficult to conceive. Imagine a game session where violence doesn't take place; where the elements and environment are adversaries rather than a bunch of mooks or minions and a big bad behind them. The extremity of a situation can be tailored by the game master to the adventurers in question.
Skill or ability checks will be able to fill a dice-roller's need for resolution while roleplaying buffs can enjoy negotiating with native locals for supplies or engaging in diplomatic relationships with a nomadic tribe as Marco Polo did while exploring treacherous mountain passes or dog-sledding over trackless snow. The dungeoneering equivalent would involve travelling through caves and negotiating with peaceful denizens for directions or food supplies.
I confess I'm writing from the position of a boyhood love of Jules Verne and exploration-type adventures here. Even the explorations of Conan or Fafhrd & The Grey Mouser have travel in exotic locations where the ability to climb glaciers or treacherous mountain passes to escape or get ahead of the enemy matters more than skill in battle or magic. Even if it does come to that in the end; the journey is often as dangerous and often as exciting as the final fight.
Trail-blazing would make a simple structure for an adventure; conquering a mountain may be an adventure in it's own right. Climbing steep cliffs, rock slides, avoiding avalanches or falling off and dealing with extreme environments that can be found (hypothermia, a lack of oxygen, treacherous ice) may provide plenty of challenges and entertainment. Treasure may be found in the form of mineral wealth, animal nests or even the remains of former mountaineers.
Discovering a new trade route for ships is another adventure to consider. The exploration of islands with drinkable water and food may become a primary concern. Dealing with your unruly crew, charting navigational hazards (sargasso) and surviving storms. Treasure may take the form of pearls (extracted from pearl beds), gold left as offering in abandoned temples to pre-human deities (complete with traps and possibly a curse) or even exotic livestock.
Another alternative is the foundation of a frontier settlement; finding food and shelter for your party, making deals with merchant traders, settling peacefully with neighbours, managing prospectors who discover gold in the hills nearby and who wish to tear up your settlement with their new wealth, avoiding pacification by soldiers wanting to horn in on their good fortune and acknowledging the rulers who gave you the charter to explore in the first place.
Combat is a form of conflict that is readily accessible to an audience; it is however not the only game in town - there are other ways to challenge adventurers and despite Alexander the Great, a sword doesn't solve everything. Exploration and taming the wildnerness is a part of adventure and presents a different challenge for those facing a never-ending stream of combat in the dungeon (or dungeons) of their campaign.