What details do we have about the buffer overflow protection on the Xbox? Is it nothing more than stack pages marked as non-executable? (NX bit?)
If that is the case, then our job is certainly a tad more difficult. But as a reminder, non-executable stack does not mean that we can't have buffer overflows. The memory is still corrupted, return addresses can still be overwritten, it's just that any shellcode cannot execute. The common workaround for this has been to jump to a widely available and statically located library/system call, or at the very least an address in the executable that is known to be a useful function, and include your parameters on the stack. As an example, on a windows machine with buffer overflow protection, you can overwrite the return address to point to ShellExecute and slap a string on the stack to run whatever command you wish.
Some information on available API calls on the X-360 would be great, perhaps a little peek at the import table on an available executable. Surely there's a single command to launch an XBE/XEX, but the question is does it have to be local? Can you pass it a remote URL?
In our case though, a single command isn't enough. Call it a longshot, but what if we could hijack two consecutive return addresses? The first jumps to a pre-existing routine to copy a chunk of memory to another location (Such as memcpy, you don't get more standard than that) while the second jumps to said new location, in effect relocating our shellcode to an executable codepage. That would take some careful stack manipulation and debugging abilities that we don't have at this point...unless someone has a dev kit. It also assumes a lot, for one thing that the heap is executable or the code pages are writable, both of which are doubtful.
Just putting it out there.