Do you think its plausable to make a game like this?

certainly. pretty much every game i've ever made is all random (within reason of course). the whole idea is even the developers won't know what's going to happen next.

Would it be hard to make it fun since story and quests are not hand-made?

no. example: SIMTrek/SIMSpace is a random mission based starship flight sim. when first released, it was a top ten download on AOL, 10,000 copies downloaded the first week.

however, randomly generated storyline based games can be difficult. procedural story generation is still in its infancy.

Would it feel repetative, or could it give replayability? (would you want to play another "campaign" after beating the game on a harder difficulty setting?)

it depends on the amount of variety you program into it. SIMTrek started with 20 types of missions, then jumped to 53 or so, then went with mission generators driven by campaign generators, driven by a politics engine. about a dozen types of campaign generators, perhaps two or three dozen types of mission generators, with a typical mission generator creating anywhere from a few dozen to tens of thousands of possible missions, and that's before you even get into number appearing and initial placement. i never figured out exactly how many types of missions were in the game, probably somewhere between 50,000 and 100,000.

with games like this, that you can play again and again, the player will play at a difficulty level which they are comfortable with. over time, they will increase difficulty as they get better. so they may end up playing a couple dozen games at each difficulty level.

A completly random world is common in roguelikes and survival games, but would it work for such a game? What would be the difficulties?

procedural content generation can work for almost any game. the trick is to generate content which is as good as you can make by hand.

note that going procedural will give you a different types of game. IE mission based (defeat the ten bases), as opposed to storyline based.

Rather the game will center around clearing 10 or so enemy bases/camps of increasing difficulty.

this might not be enough to make it interesting. personally, it doesn't jump out at me as being cooler than a one shot disposable storyline based game. it would be easier to make, but you know how it is, you get out of something what you put into it. cool games are work, whether procedurally generated or made by hand.

i'd focus on this and try to come up with something that would obviously be WAY cooler than the storyline version. to do this, i'd recommend forgetting about mechanics and implementation for a moment. focus on the core aesthetic, and answer the question: "wouldn't it be cool if there was a game where you could ___________ ?" or in your case:

"wouldn't it be cool if my game was a game where you could ___________ ?". you've got the engine to out-fallout fallout3 in a 2d way. go for it!

more examples:

in SIMTrek/SIMSpace, you fly around in your starship, and get messages and orders from starfleet from time to time - just like in the TV shows.

in Caveman, its a FPS/RPG that's evolved into a true full-tilt paleo-world simulation. its just like being alive 50,000 years ago. and its ALL random. being based on D&D and Traveller RPG's as opposed to FPS games, it uses random encounters, not spawn points.

in general, i make games_I_ want to play. so they have to be as random as possible so they aren't predictable, and i can enjoy them.

note that nothing says you can't do a random game and add non-random elements such as hard coded quests, hard coded scenarios, and/or hard coded storyline campaigns.

1) If your main goal is to reduce workload on yourself you might be disapointed, typically and usually handmade is easier & faster to make.

2) Split your question into categories. Like random loot is extremely easy to make and give you big time savings. Similarly monsters/nenemies placement is quite trivial to randomize. Map is much harder to do but on the other hand it might be a time saver (prefered appoach is mixed random + handmade). Random quests are almost impossible to make :) Whole campaing being random is both impossible anfd pointless (because it's trivial to do handmade).

A completly random world is common in roguelikes and survival games, but would it work for such a game?

In short do not go for a 0/1 approach, use fuzzy logic :) Some things random, some handmade, some semirandom using handmade modules.