I was just facing the same problem and came up with the following solution (assuming the language you're using to implement your interpreter supports exceptions).

1. Make sure your AST nodes can be uniquely identified (unique ID, pointer/reference value, etc.)
2. When constructing your AST, make sure you have some way to represent a (block) scope, either explicitly with a "Block" node or implicitly via some "isBlock(node") function
3. When encountering a 'goto', resolve the destination AST node. Then pass the identifier (or even the AST node instance itself) along with your exception (in Java this can be done with a member field in a custom Exception subclass, in other languages you may need to encode it in the exception message string etc.).
4. When interpreting a block scope AST node, loop over the children of this block and have this loop wrapped in a try/catch(GotoException). When you catch a GotoException, check whether the target AST node is a direct child of the block scope that caught it. If the target is a direct child of the current block scope, restart execution at that node. If not, re-throw the exception so the next block scope higher up the call stack can have a look at it.

Definitely not very performant but much easier to implement than "flattening" your AST (if you start going down that path you might as well write a compiler instead of an interpreter).