How to install ubuntu in UEFI mode

In brief:

• Use a 64-bit Ubuntu -- The vast majority of EFI-based PCs use 64-bit firmware, and Ubuntu is set up in such a way that you can only install a 64-bit Ubuntu on such systems -- at least, by default. (It's possible to jump through hoops to install a 32-bit Ubuntu, but there's seldom any reason to do so.)
• Disable Fast Startup and Hibernate in Windows -- These Windows features are likely to cause filesystem damage in a dual-boot environment, so they must be disabled. See here and here for information on doing so. Note that the Windows Fast Startup feature is entirely separate from a feature in many EFIs with a similar name. Disabling the EFI feature is seldom necessary (but sometimes it is). It's unclear from your description whether you've disabled the Windows or the EFI feature. A failure to disable these features will not have caused the problems you've encountered, but will cause problems down the line, so you should deal with them now.
• Disable BIOS/CSM/legacy mode in your firmware -- In most (but not all) EFIs, this option, if active, makes it possible to (but not certain that you will) boot in BIOS mode. Completely disabling this option usually (but not always) prevents booting in this mode. Naming of the CSM feature varies from one system to another. Usually it's a feature you must disable; but in some cases you must instead set the boot mode to "UEFI only" or something similar.
• Prepare the boot medium properly -- If you use a tool to turn a .iso file into a bootable USB flash drive, that tool might or might not copy the EFI boot loader to the USB flash drive. Even if the EFI/BOOT/bootx64.efi file seems to be present, an EFI might not like some detail of how the USB drive was prepared (like its partition table). Trying another tool may be necessary. Rufus generally does a good job of this. I provide additional comments on this at the end of my CSM page, referenced below.
• Use the appropriate boot option -- In many cases, you'll see two boot options for an external boot medium in the computer's boot manager. One of these options includes the string "UEFI" and one doesn't. Pick the one that includes the "UEFI" string; if both are present, the other one is likely to boot in BIOS mode.
• Use "Something Else" -- In many cases, once you get the installer to boot, the "install alongside" options are missing from the Ubuntu installer's menu. This is simply a limitation of the installer, and you must use the "Something Else" option (as described here) to work around this problem.

Note that disabling Secure Boot is seldom necessary. Ubuntu supports Secure Boot, and it normally works fine. There are rare cases of incompatibility because of bugs in the EFI and/or in an Ubuntu component, but these normally cause the Ubuntu installer to fail to boot. Secure Boot can also complicate use of some third-party drivers after booting.

For more information on this subject, I recommend you read:

• Adam Williamson's blog entry on how EFI works -- This page describes the theory behind EFI-mode booting.
• A question and answers on the differences between BIOS and EFI booting on Superuser.com -- This provides the basics of the preceding, but is more concise.
• My page on installing Linux on EFI systems -- This page is a more practical introduction to EFI-mode booting than Adam Williamson's blog.
• My page on the CSM -- This page covers the CSM, including when it's useful and when it's not.
• The Ubuntu community wiki entry on UEFI -- This page is a bit disjointed, but is the most Ubuntu-specific introduction to EFI and its issues.

I spent a whole day trying to figure out what to do, I tried all possible combination in my BIOS setup and it didn't work.

Then I read in some forums that Windows program Rufus, can create an Ubuntu bootable USB with the UEFI setting enabled.

When trying to create the bootable USB, I opted for GPT instead of MBR (you'll see the setting when you'll see the Rufus GUI).

That did the trick!