First, disable Secure Boot in your firmware. This might or might not be the source of your problem, but it is a possible source of problems, and if you're experiencing some other problem, you might fix that problem and then run into a Secure Boot problem, which might make you think that your fix was ineffective. Thus, disabling Secure Boot is in order. If you want Secure Boot to be active, you can try re-activating it once you've got the basics working.
With that done, you might try booting with a USB flash drive or CD-R version of my rEFInd boot manager. If you can boot rEFInd, it should show you option to boot both Windows and Ubuntu. Test them both. If they both work, you can install rEFInd to your hard disk via the Debian package or PPA. Alternatively, once you've booted Ubuntu via rEFInd, you can install the grub-efi package in Ubuntu and then run grub-install. This will install GRUB to your hard disk, which should work -- but because you didn't boot via GRUB, that's not quite as certain.
Backing up again, the symptoms you report generally indicate either a Secure Boot error or an improperly-prepared boot disk. You say you've tried preparing your USB drive "thousands of way[s]," which of course is an exaggeration. It's possible that you made some fundamental error in all of your attempts; or perhaps your firmware is very picky and you happened to use methods that ran afoul of your firmware's pickiness. In any event, trying (yet) another tool may work.
As I said, Secure Boot is one possible complication. Ubuntu is theoretically compatible with Secure Boot, and in practice it usually is. Some EFIs, though, are picky or buggy. I know of two specific problems that can occur, and which have different solutions:
- Buggy firmware -- One computer I own (an Intel NUC DC5427HYE) came with firmware that refused to recognize Ubuntu's Shim. (Shim being a program signed with a key that Microsoft uses for third-party boot loaders.) It should have accepted this key, but because of a bug in the firmware, it didn't. Updating the firmware to the latest version fixed this problem and enabled the system to boot. I've heard of similar problems with some other computers. Such problems are rare, but if you happen to be running into it, updating your firmware (what the manufacturer probably calls a "BIOS") may fix the problem.
- Missing Secure Boot keys -- I've corresponded with one person who discovered that his computer had the public key tied to the one that Microsoft uses to sign its own boot loaders, but lacked the public key tied to the one used to sign third-party boot loaders (including Ubuntu's Shim). Thus, this computer booted Windows just fine, but wouldn't boot any third-party tool. The easiest solution in such cases is to disable Secure Boot. If Secure Boot is a requirement, the only option is to take full control of the computer's Secure Boot keys, as described on this page of mine. Taking this sort of control is beyond most peoples' comfort zones, but it is possible.
Both of these problems present very similar symptoms. The easiest way to distinguish between them is to type efi-readvar (this command comes in the efitools package, which you may need to install). Look for the following line in the output:
C=US, ST=Washington, L=Redmond, O=Microsoft Corporation, CN=Microsoft Corporation Third Party Marketplace Root
This line is part of the identification of the public key required to run Ubuntu's Shim, so if it's not present, you're faced with the second problem I identified; but if it is present and an Ubuntu disk boots OK with Secure Boot disabled but not with it enabled, you're probably facing the first problem. Note that the key part of this line is near the end -- namely, CN=Microsoft Corporation Third Party Marketplace Root. The key Microsoft uses to sign its own boot loaders is similar, but reads CN=Microsoft Windows Production PCA 2011. Ordinarily, both keys should be present (along with some others).
