I'm interested in learning more about putting the shellcode into an executable. I suppose my first step would be to use C code of a Windows "Hello World" executable, ideally compile it on BT4 using gcc and run it on a variety of Windows PCs to test that the code and compilation process work. If my thought process is correct, I might have to have a long think about the second part though which is beyond me (at present) - adding some function calls to get RWX memory and run encoded shellcode. Do you think I'm on the right track? Do you have any more tips? I'm quite happy to hit google
You're on the right track. Mine is done in C++.
It strikes me though that I'd still have to work on getting the executable to be run on the victim computer. I don't know any way of uploading such an obfuscated payload or executable via Meterpreter to gain a Meterpreter session.
Yep, but social engineering isnt as hard as you think

Finally, I saw a video of Muts running through the process of creating a code cave to hide code and bypass AV. I think it was called something like "I'll piss on your AV" (no offense intended to anyone!). He used ncx99.exe, as demonstrated in your second link.
They actually incorporated that into the OSCE course... The problem with the code cave is that a lot of the AV vendors will pick up the "stub" but there are ways around that too!