Not so hard, really. Harvest Moon does all of those things, and it has a pretty solid fanbase.
I think the difficulty would be making a FUN free-roaming, non-violent game.
A few ideas would be an exploration title--full on puzzles, dangerous pitfalls an environmental hazards, but no combat.
I had had an idea for this sort of thing a few years back, actually.
The game's setting could be altered--in my case, I had it about a team of explorers investigating the ancient underground ruins beneath a steampunk city, which was so very large that the entire game took place in this one, multi-layered area. Combat was sparse, if at all--any dangers you encountered were either in the form of pitfalls, falling rubble, team mutinies or other problems. I had kicked around the idea of having parts where you were attacked by unkillable ghosts or something, or maybe chased by some strange beast, but the point of the game was purely on exploration and puzzle solving.
A lot of inspiration was taken from Metroid Prime and Silent Hill--your team would be a small, compact group with various skills per member that allow you to progress further down. You would find writings, murals, graffitti or other such "logs" or "journals" that explained the history of the world you were exploring, and the storyline would be driven by a strong sense of atmosphere coupled with the slow reveal of shadowy details by the discovered messages. There were to be nine very large levels, each with a different environmental theme--the first one would be a lot of disused sewer tunnels or other things more directly connected to the world above. In fact, one puzzle/trap involved you finding a guy atop a huge solar panel. The guy was stripping the panels off to sell above for profit--which would be an example of salvage that you could do--when the ceiling above falls apart. Sunlight pours in, activating the solar panel, and the sun slowly starts to cast an intensified beam across the panel's surface. You, the player, then have to scrabble up the tilted platform, using broken off panels as hand holds in a race-against-the-sun to get to the other end and safety. The poor bastard stripping the panels would get incinerated, to showcase the danger you are in. However, by the ninth and final layer, you're in a strange, almost alien sort of world, where there's little ground to speak off--floating islands, strange bubbles and bright, vibrant colors abound, and the player at this point has to create temporary bridges from place to place, requiring at least one team member to cross a chasm on a single rope in order to then secure a more stable means of crossing on the other end.
Additionally, there would be a second subplot to the game involving your team members themselves. There's a team stamina bar, of sorts, and when it gets low, everyone gets sluggish and less capable of doing their tasks. So, it's important to rest and recover, and while resting, you can sit in a circle with your team mates and interact with them--learn their backstories, get advice or comments on the current situation, and eventually learn information that can trigger sidequests and the like in the upper city--which you can return to in order to sell salvage or valuable news of your discoveries.
It would be a LOT like Ico in the sense that you are solving seamlessly integrated puzzles built into the environment itself, and as you can see, there is absolutely no need for combat whatsoever.