How can it be "entirely new", if it is based on Android?
"Modified" to your liking, is not new.
The same way Android is based on Linux but isn't Linux?
As far as what language? Most OS' are built on some branch of C/C++, so that'll be what you'll likely use. Those languages are established, robust and pretty feature rich, but they're not particularly easy to get used to.
That's kind of a trade-off with computer languages, either you get simplicity of use, or you get a more solid end product. I.e. HTML is pretty damn simple to use, but you wouldn't (couldn't) code DOOM 3 with it.
No, you don't need a compiler on your phone. You'll do pretty much everything except testing the OS on your computer (and even then, you'll probably try testing the OS on the computer, too. Perhaps through the Android SDK emulator.). It's like with console games. They don't actually program on a Playstation 3 or an Xbox, but they have development kits that contain the necessary resources to compile the code on a PC into something that will (if the code's right) work on those consoles.
How much programming and development experience do you have? I'm thinking not a lot, judging from your questions, so I would strongly suggest starting smaller.
When I first got interested in programming, I also wanted to build an OS. One with the stability, robustness, configurability and general "cool factor" of Linux, but 100% compatible with Windows and thus freeing people from Microsoft's grasp without having them sacrifice the software they already have (that there is no open source alternative for).
Of course, I had no idea how hard it was and promptly abandoned that when I started doing some less-intensive software (first year programming courses, make a basic "slot" machine, a survey system,"Hello World", etc.) and started to figure out exactly how much work it was.
Remember, Google, Apple, Microsoft, and all the different Linux Distro providers, all have teams of developers and designers working on these OS', many of which only focus on a certain part of the OS (like some will focus on the UI, some on driver/hardware interaction, some on networking interfaces/protocols, etc.)
just let google and Mozilla work it. Making a full os is not fun.. I've tried. And got it to work. But its not what you think.