Copy and Paste. You'll probably want to design the unique elements somewhere (in-game or in an image editing tool), then build them once in-game and copy and paste them in-game using a mod to create the large structures you're looking for.

WorldEdit has copy/paste support but loading it in Single Player requires some careful modifications. It's a bit easier to install if you're working on an SMP server.

For designing your project... Minecraft is really best. Be prepared to build a lot of temporary stairs to stand on as you test out designs. Or install a flying mod.

I would highly recommend the WorldEdit feature.

You could also use the TooManyItems mod for an in game inventory editor and you could install zombe's modpack for the flying ability.

Looking up a few tutorials can't hurt either. Check YouTube.

You can use Paint or Photoshop or indeed any image manipulation program for planning and you could ask a few friends for faster construction.

But in my opinion, MCEdit is the top of the hill when it comes to building giant structures.

Creative mode can be a major boon for this if you just want to build. Flying helps with tall structures.

Otherwise, I suggest doing it in multiplayer, since you'll probably want some people restocking supplies while others use them up.

Creative mode is a good idea because you will have unlimited resources to use plus the ability to fly. This sounds like just what you need for this kind of tall and complicated project.

Although most people recommended the use of either 3rd party tools or creative mode, if all you are going to do is a stone castle, then you can do a rig similar to this one:

 M *W
 *  *

(height of wall)

XX XX    * - blocks
XXXXX    X - ground

This is a cross-section of a rig that enables "fast and effortless"¹ construction of pure stone walls.

Essentially, you place a magma source (from a bucket) in a high stand (height of your wall), surrounded on the side you don't want magma to flow by non-flammable material. The magma will flow 4 blocks sideways and afterwards will fall down. As soon as the magma curtain is formed, you can then pour water on the sides of the wall. As water flows faster than magma, the wall will be formed as soon as water reaches the ground.

You can then reuse the magma and water. This single rig can make walls with about 9 blocks width. You can combine more to make bigger walls. This is very useful if building in height as you don't need to process or place the stone blocks. This can't do the castle's floors, however.

^{1 - If you consider fast and effortless picking up a bucket of lava and another for water and then building a scaffold, which you would also need to build regardless.}

^{2 - I've done this in head only, relying on physics that might have changed since the last time I played the game.}

I'm assuming you are doing the building in survival mode, and don't have access to creative mode flight...

How can I effectively accomplish the task without running, climbing etc. around a lot, trying to get up to a wall in order to reach somewhere etc.?

Ender pearls! They take some time to get used to, and some practice using them properly, but once you have used them for a while, you will wonder how you survived without them. All you do is right-click with an Ender-pearl in your hand, and you will be instantly teleported to where the pearl landed, which is great for getting up to the second floor of a building or similar without needing to build a temporary stair-case to get up there.

Ender pearls are quite rare in the overworld, so I would recommend getting to The End and setting up at least a small, simple Enderman farm there.

Sand Pillars! When that is not an option, and you need to pillar up to high places, I would recommend towering up using sand. Then, when you no longer need your temporary tower, you quickly replace the bottom block with a torch (or use something like this), and the entire sand tower is removed without you needing to waste time and tool durability mining/digging away the temporary tower.

use blocks that stands out to mark things on the ground and use dirt block to build stairs to get to the top of the building such as a flag. Also use wood or block that can be easily destory to build the frame of the building.

The best laid plans O' Mice An' Men...are the ones that will probably be finished.

Assuming you want to do this in Vanilla, without any Mod help or copy/paste, here's how to go about building something enormous.

Calculate

Before you even get started, you need to calculate how much material you're going to use to build it, and how much space. If you're willing, you can open up a SuperFlat Creative world in order to get a good idea of how big your structure should be. This is where your grade-school math skills will come in handy for figuring out how many blocks it will take to complete your structure. Keep in mind the type of material you want to use, and use the width, length, and height of your structure to get a general idea of how much you'll need (always overestimate - it's better to go in with more than you need than it is to have less).

Harvest Resources

It's going to take a lot of resources to build this super structure, and unless you're using creative cheats, that means a lot of time gathering up things before you even begin. If your structure is primarily made of wood, find out what type of wood you want to use and build a tree farm. I like to lay down sand and patches of dirt to help space the trees out, but this isn't entirely necessary.

If you're building out of stone, find a hill and dig down dig down into the earth as deep as you can. You may want to start a branch mine just to gather rare minerals while you're mining for stone anyway, and to build a rail system to transport the raw materials back up to the surface.

Either one of these farming tasks should take place near where you're going to eventually build your structure. Which leads to, assuming you haven't already chosen...

Scout a Location

Location is absolutely key for any major construction, and you're going to want to pick a good one first. You may already have a location in mind, in which case you can skip right past this step.

A good location should be near something important - a coastal area, or a river crossing, somewhere that will be memorable, since you're going to be spending so much time working on it, it'd be a shame if it were up on top of a mountain where no one will ever go (though leveling the top of a mountain for your castle WOULD be impressive...)

Flatness is imperative, but if you haven't got a flat surface, you can always make one. TNT can help, but you'll eventually have to switch to basic shovels and picks. Put some efficiency or unbreakable enchantments on them to make the job more bearable.

Build!

If you've done the previous steps correctly, you should have more resources than you need to complete the project. Resource exhaustion can be one of the most frustrating parts of crafting a megastructure, which is why most of the prep here is not in planning out the shape, but in making sure you've got enough. By preventing yourself from getting into a position where you'll have to keep going back underground for more and more resources, you avoid getting burnt out, and can construct your new fancy megabuilding to your heart's content.

Use the /fill cheat.

This helps create large planes or cubes of blocks using coordinates and Minecraft IDs. Usage:

/fill (X1) (Y1) (Z1) (X2) (Y2) (Z2) minecraft: (the item you want it built out of)

Have fun!

Edit: Use the Minecraft id "minecraft:air" to clear out an area, to "erase" the land.