You could look at rolling wave planning.
Under rolling wave planning, you only have a detailed plan for a small block of time, perhaps as little as two weeks. You also maintain a "cloud" of tasks that you know that you eventually need to do, but you don't know how to do them, when they need to be done, or dependencies between them. Tasks can be added or removed to this cloud throughout the project. You also have milestones and a final goal that you keep moving toward.
On a continuous basis, you revise your detailed schedule using known information. How you maintain that detailed schedule is up to you - it could be a WBS, a Gantt Chart, or something else entirely. However, it only contains a small segment of the project, that which is known at the time. As you gain more information and it becomes possible to do new things, you can move tasks out of the cloud into the detailed schedule, add tasks to the cloud, or delete tasks that aren't actually necessary from the cloud.
You can couple this with a stage-gate approach. A stage could be a time boxed interval or at the completion of a milestone, in which you review progress and determine if it's feasible to continue the project.
There are some blog posts about rolling wave planning: Johanna Rothman, PM Crunch, and Project Management Knowledge.