Imagining a reduced control system with a single joystick and one button ("confirm") lets us simply the problem a little bit first.
The usual frustration with on-screen keyboards is that they implement a grid search: your target is found in one of 3 or 4 rather long rows, and you must traverse each unwanted target between your current position and your target. While your eyes can mostly instantly locate your target — if only because of familiarity with QWERTY, not because there's any actual logic to it — your hands have to traverse a lot of non-targets. This is very slow. You could potentially improve it by using the joystick as a cursor/pointer rather than as up, down, left, right, which would allow faster targeting by gliding over non-targets in two dimensions at once (at the expense of accuracy for unskilled users).
An optimal search, on the other hand, would be a narrowing search: where all doors are equally accessible at first, and they lead to more doors of similar accessibility. This is the idea behind phone keypads, for instance. Give me 9-12 buckets instead of about 30, then make each bucket contain 3-4 keys, and I'll be more than twice as fast.
A good modern version that can use joystick targeting more fluidly would be a circle menu.
Give the user 4-8 initial buckets; more is too hard to hit accurately and quickly. When they hover over one, reveal more. As in the image here, if you reveal more as an extension of the original direction — rather than by replacing your original menu — you can allow for quite fluid motions, as well as allowing the user to go back a step easily by simply reversing direction. What's more, if your layouts remain predictable, over time they will build mental pathways for individual letters, e.g. 'a' is ← ↑ or 'e' is ↑ →. Because these are motions on a joystick, they become fairly easily cemented as muscle memory.
What should your buckets be? You could go a few ways. One would be, like the keypad, consecutive blocks. That would be familiar and fairly logical. However, there are too many to fit in an accessible circle unless you make the buckets bigger, which reduces the familiarity factor. Another option would be letter groups, e.g. vowels. If you were to do some serious research you could make it linguistically informed according to spelling patterns (e.g. 'ng' in the same bucket since they commonly collocate...), which could lead to a very efficient keyboard at the cost of a greater learning curve and possible user rejection. Or simply try different options and do user trials.
Once you have that in place, what do you do with your extra buttons?
- Backspace the last letter
- Clear the word
- Shift; hold for caps lock
- Switch to number mode (not ideal but again, too many buckets is hard to use with a circle menu)
- Move cursor back to initial circle, i.e. reset current choice