How to tell if I'm good enough for graduate school? I'm concerned about my level of preparation for graduate school. I have decent grades (3.64 GPA, 4.0 in math), great recommendations lined up, and some OK research experience (no publications), but I really don't feel like I'm ready for the next step. 

I'm interested in applied math, and was a physics/computer science double major for most of undergrad, switching into math just last semester. I'm taking Analysis 1 now as a first semester senior, and it is the only pure math class I've ever taken (though I've taken a bunch of applied courses and semi-pure courses, like advanced udergrad ODEs). I'm doing very well in the course, and I'm really enjoying it, but I feel that, because I'm so late in joining mathematics, I'll be really behind everyone when I get to graduate school, if I do get in somewhere decent. My scores on practice tests for the math GRE are in the mid 600's, and that makes me feel like a phony as well (although I haven't really studied that hard yet, maybe they'll go up? Also, its a good thing many applied programs don't care about the subject test...). Sure, I have some skills from my background that other students don't have, such as non-trivial software development and an ability to solve difficult physics problems, but when I look at the profiles of the 'good' people on this website, or talk to my friends that have been doing math olympiads since they were 3, I feel like there is just no way I can be good enough for a career in mathematics given my 'late' start.

Is it possible to catch up with others at this stage? Will I be doomed to a life of constantly being behind those who are smarter than me? Has anyone ever built a strong career from my kind of situation before?

I just wish I had some more time...
At my university we use baby Rudin, Dummit and Foote, and Munkres in the first year analysis, algebra, and topology courses (respectively), which is the average schedule for an incoming grad student.  You can also test out of these and move to the 2nd year if you happen to be good in one of those fields (or two, if you're really exceptional).  My opinion is that most math majors could handle this schedule given an appropriate amount of studying.  Worst case you can opt out at a master's if you decide you don't want to do research.

As far as being stupider than other people goes: of course you are.  Unless you're the smartest person on earth, there are smarter people, and if you spend your time sitting around thinking about who's smarter than who, they're all you're going to pay attention to. If you're getting a math degree, you're probably pretty smart, and that's good enough.

I embraced my own stupidity long ago, and in doing so, I gained the ability to ask questions without losing face.  Instead of worrying about other students knowing I'm not a genius, I can talk my problems out with them, gain their insight, and learn from my own mistakes.  For whatever reason, people in the mathematical field have this tendency to try to convince you that you're too dumb to do anything. Don't listen to them.  If I miss a proof, I'll get mad, reread the chapter, work book problems, harass the professor, and stop sleeping until I understand everything. Be stubborn, not smart. You've got to have grit.
You just take courses and if they are too hard you take them again or take easier courses. I will suggest if you ask for math you can prepare yourself with taking this course it probably the best out there it wont make you Gaus but it will soften the conceptual barrier which is what you want to do.

The course have started but if you have some time you can go through it and also Kieth is very nice, your goal should be to be conceptually prepared, but a university basically is an institute that suppose to arrange you the condition to overcome that state in its essence: 
https://www.coursera.org/course/maththink