Building effective external DSLs
I've written DSLs in Boo, Irony.NET and a toolkit called Grammatica. You say that a parser-generator is too complicated, but you may be being too hasty in your judgment, in fact they are quite simple to use once you get over a small learning curve, and open up a vast world of possibility that easily overrides the effort. I found learning the notation required to write grammars for most parser generators somewhat similar to learning Regular Expressions - you have to bend your mind just slightly to let them in, but the rewards are significant.
My opinion is this: If your target language is simple enough that it could be handled by a dumbed down visual designer, then writing a grammar for it using a parser generator should be quite easy.
If your target DSL is complicated enough that you'll need to break a sweat writing a grammar, then the dumbed down visual tool won't cut the mustard anyway and you'll end up having to learn to write a grammar anyway.
I agree in the long term about internal vs external DSL's, though. I wrote an internal DSL in Boo and had to modify my DSL syntax to make it work, and it always felt like a hack. The same grammar using Irony.NET or ANTLR would have been just as easy to accomplish with more flexibility.
I have a blog post discussing some options. The post is centered around writing a DSL for runtime expression evaluation, but the tools are all the same.
My experience with Irony.NET has been all positive, and there are several reference language implemented using it, which is a good place to start. If your language is simple, it is absolutely not complicated to get up and running. There is also a library on CodeProject called TinyParser - this one is really interesting, because it generates the parser as pure source code, which means your final product is completely free of any third party reference. I haven't used it myself, though.
If you're looking into writing stand-alone DSLs, then you're looking into building compilers--no way around it. Compiler construction is essential programming knowledge, and it's really not as difficult as commonly thought. Steve Yegge's Righ Programmer Food summarizes the value of knowing how to build compilers quite nicely.
There are plenty of ways to get started. I recommend checking out the 2 papers mentioned in the article: Want to write a compiler? Just read these Two papers. The first one, Let's build a compiler, is very accessible. It uses Turbo Pascal as an implementation language, but you can easily implement it in any other language--the source code is very clear. Pascal is a simple language.
Once you get a good feel for how things work and the terminology involved, I recommend delving into something like ANTLR. ANTLR has a nice IDE, ANTLRWorks, that comes with an interpreter and a debugger. It also produces really really good visualizations of your grammars on the fly. I found it invaluable in learning.
ANTLR has several good tutorials, although they might be a bit overwhelming at first. This one is nice, although it's against ANTLR 2.0, so you might run into incompatibilities with a more recent version (currently the latest is 3.1).
Finally, there's another approach to DSLs: The Lisp approach. Given Lisp's syntax-less nature (your code is basically abstract syntax trees), you can shape endless languages out of it, provided you get used to the parentheses :).
If you do go with that approach, you want to use an embeddable Lisp. Under Java, you have Clojure, a Lisp dialect that interoperates flawlessly with JVM and its libraries. I haven't used it personally, but it looks good. For Scheme, there's GNU Guile, which is licensed under LGPL. For Common Lisp, there's ECL, also under the LGPL. Both use a C interface for interoperability, so you can pretty much embed them into any other language. ECL is unique among Lisps in that each Lisp function is implemented as a C function, so you can write Lisp code in C if you want to (say, inside your own extensions methods--you can create C functions that operate on Lisp objects, and then call them from Lisp). I've been using ECL for a side-project of mine for a while, and I like it. The maintainer is quite active and responsive.