I’ll write an answer as a person who have never been to India, so it may be that my perception is completely wrong (I’m definitely going into some kind of guessing in a few places) - sorry in advance.
One thing which has been pointed in other answers already is coverage. I believe there are quite a lot of people who may find problem solving interesting and enjoyable, yet they are not aware of it. I am from Ukraine, and I discovered competitive programming in 10th grade because of folks from ICPC team Scorpions which represented Lviv National University at ICPC 2008 and got gold there. These guys were doing their best to promote this activity, and they just gave some promo speech about it at some local olympiad (I’m not even sure if it was informatics or not), showing how cool it is and giving link to local online judge.
Still my first motivation was to simply get diploma at national competition because back then prize place at national competition in any discipline guaranteed university enrollment 
Making people know about it while they are still in school is a good idea; generally you don’t really need to have competitive programming as a school subject on national level - it is not like that in Ukraine, Russia etc. But having something related in some specialized schools is a good idea.
Generally you need some way to reach out children to show them what competitive programming is and why it may be cool - even cheap trash like “it’s a way to get job at Google” may work, but I’d prefer being more honest on it and putting different priorities there So these who find it interesting will give it a try, and they’ll enter university with better background and enough time to reach higher levels.
Having some training groups / classes / volountary courses at least at schools with stronger students should also help to both increase coverage and find those who are interested and can do well.
I don’t know how many people in India are doing competitive programming at any serious level. I believe that doing it actively for 4 years should be quite enough to reach red ratings starting from scratch, so India not having many red contestants may be not about starting late (which may be the case for not having elite level contestants) but about not having many people doing it actively. I know how training of the team who won ICPC Finals this year looked like - that’s about having 3-4 team contests per week plus multiple training camps for several years, and then increasing intensity to basically having a training each day (with some exceptions) for last half a year before finals. In case there are teams in India who do 200+ team contests per year plus upsolving plus individual practice for several years in a row, and they can’t reach some decent level - I don’t know what’s wrong and how to help them, because I really believe that intense practice should give results even if it is done not so properly.
These “where to start” and “in which order to learn stuff” things don’t make much sense to me - at least on the upper part of the scale. There are always some exceptions, but I personally wouldn’t expect much from people who aren’t even able to use Google. I mean - show them what competitive programming is, show them how Google works, and that’s enough. Developing community may matter a lot though. For a lot of people having somebody to discuss stuff with / to compete against is helpful or motivating. In Russia strong teams nowadays are attending at least 4-5 training camps per year (often even more). When I moved to Russia for a year to participate in ICPC over a course of 10 months I participated in 5 training camps - as far as I remember I tried to recall it now, and these 5 are only camps which I recall, but I’m not even sure that there were no other camps in between I don’t know how many training camps are there in India, but probably it is not like that.
Giving more motivation by increasing number of ways to get prizes, number of different contests/camps etc. should work. Also, emphasizing some stuff during promotion may matter. People believe that in tier-3 college they have no chance? OK, pick a few guys from such colleges who reached good results and use them as an example. I bet if you’ll take some guy from company like Google, who finished tier-3 university and he’ll visit some “not-so-good” college and tell his story - some people may get interested or even motivated.
Imagine this story: “I finished university X - just like your, it’s not so well-known. It’s not like one of these top universities where you have 10 big companies coming for placements - nobody knew about mine, and I’d probably have hard time getting noticed by Google or Microsoft. During my time there I started doing competitive programming, and I got rather well in it. It turned out to be interesting, thrilling experience; after I got decent rank in GCJ competition, Google contacted me and asked if I’m interested in internship/full-time job. I send them my CV and they scheduled interview. Tasks which I was solving during my CP years were somewhat similar to some of the tasks you have to do during interviews, so it was making things easier to me. Also, during my university years I attended several international competitions, including ICPC World Finals where you have to compete against best contestants from all over the world, and I met a lot of smart, interesting people there. Now if you want to give it a try - check sites like A and B, and maybe you’ll also enjoy it; Internet contains everything you need for preparation, so don’t worry about guys from top colleges having better lecturers. Just check it - maybe you’ll find it boring or complicated, but there is also a chance that you’ll enjoy it and turn it into way to get noticed by big companies, meet a lot of interesting people and learn a lot of interesting things.” You know, I think sometimes such stories may work.
. I dont think we can do anything about system as of now.