The Racket (http://racket-lang.org/) dialect of Scheme also provides different levels of a programming language with features of increasing complexity, for educational purposes. In the current version, there are five levels to be used while working through _How To Design Programs_ (http://www.htdp.org/). This book is geared toward adults, but Scheme/Racket is also a great language for teaching children (http://www.bootstrapworld.org/). Perhaps this can provide some inspiration for your project.
I'm not sure about the goto though (despite/because of it being something I learned as a child).
When I used goto it was in the form goto linenumber, but if you're having to create explicit labels to jump to, it would seem easier (to me) to give those labels some explicit structure as loops or functions which doesn't need to be explained at first (they can just act like goto labels) but can be built on later.
e.g. the classic:
10 print "name"
20 goto 10
in this scheme becomes
label start
print "name"
goto start
so why not
loop
print name
restart loop
and then later the label loop could become loop while or loop until or loop with item from list. "restart" makes sense both at the end of a loop and if you wish to continue with the next iteration after a test. Using goto to break out of a loop could be exit loop or continue after loop.
I'm not sure what other uses of "goto" you'd expect at this level beyond restarting or exiting loops. If/then seems to take care of simple code branching until you get to procedures.
From testing with a few children, I do feel that Basic's mandatory line numbers make usage of goto much more easier to learn. I did have to spend some time explaining labels to my students. So I kind of agree with your hunch!
I don't know with what to replace it though, it always seemed like a choice between structured loops which have their own problems (the need to explain blocks) or the return of line numbers...
Your third scheme is a new option, but not without drawbacks. The advantage of unrestricted label/goto is that the concept is learned once and applied for many types of control flow. But I think the other main case that needs to be handled is exiting loops. Maybe I could also have an exit <label> keyword, and try with some sample programs to see if it could be sufficient.
I'm still inclined towards leaving goto though. I think it's more raw and "operative" in a sense, and more creative kids might be able to come up with fun uses for it (I've recently added computed goto to the language too).
