What are any potential majors that someone can study in college that would set them up to "work for a government organization in international aid or development" or just internationally in general?

I applaud your commitment to tying your career aspirations to a global effort to make the world a better place. Fortunately for you, the international development community is made up of a diverse mix of academic backgrounds and varying forms of technical expertise. So I would encourage you to pursue an academic major that a) you're passionate to learn more about, and b) will allow your natural talents to be utilized to the fullest.

To give you an idea of the diversity of skills needed in international development, take a look at what the US government is doing to engage in, and improve upon, the lives of those in the international community. Through my employer, the US Agency for International Development (USAID), the US government addresses issues such as: agriculture, business development, conflict resolution, disaster relief, economics, education, the environment, gender equality, global health, governance, sanitation, and science and technology. And those are just a few examples from one organization; the US government has many different agencies working on an array of issues at the international level.

The list above clearly suggests there is no one-size-fits-all approach to launching yourself into a career in international development. However, there are a number of relevant skills most, if not all, of the people working in these respective areas have come to know, and certain undergraduate majors can be of immense benefit in helping you to acquire them as well. In no particular order, the following is a list of a few academic focus areas that will serve you well at the start of your international development career:

a) international political science / public policy / international relations - provides a deep understanding of governance structures, policy implications and the evolving theories of international relations (i.e., why countries behave the way they do)

b) international economics - provides a background into the fundamental theories of economic growth and development, as well as an understanding of market dynamics and their relationship to public policy

c) regional specialization / language studies - for those gravitating toward working in a particular geography, these majors provide a thorough understanding of the economic, historical and cultural considerations which necessitate development in a particular region

As a point of departure, regardless of which major you pursue in college I would highly suggest getting involved in international trips, internships abroad and anything else that can expose you to developing countries. Having past international experiences to discuss in job interviews after college will be essential to getting your dream job.

I would combine International Relations with whatever major you are interested in (you stated you are interested in religion). Maybe consider business or a foreign language or applied linguistics too.
I don't know if you can "set yourself up" with going in a specific direction in College. Your focus and job choice may play a bigger role in becoming involved in international organizations. Network during your college years with people who work in those fields.

I agree with Joe's comment above - that majoring in something you are passionate about is important, but in regards to your goal starting with international relations is best. I do also especially agree with his comment: “As a point of departure, regardless of which major you pursue in college I would highly suggest getting involved in international trips, internships abroad and anything else that can expose you to developing countries. Having past international experiences to discuss in job interviews after college will be essential to getting your dream job.”

Working in recruiting I have come to realize that it is extremely important that as a candidate you try to show skills and experiences that make you stand out from other candidates. If international aid or development is your goal – start volunteering with organizations that have causes you are passionate about. This will show your commitment and passion.

If your college offers it – participate in the Model UN and be a delegate. (http://www.unausa.org/global-classrooms-model-un/how-to-participate) I did this and you will learn a lot about the policies and protocols that are followed amongst countries and it will give you the opportunity to work with other college students from around the world.

If you are also interested, you can join the Peace Corps. I did not do this, but know many others who have and they said it was the best experience they had. You can integrate Peace Corps service with your Masters degree so you gain additional education and skills to serve overseas—and it allows you to earn your advanced degree along the way. (http://www.peacecorps.gov/volunteer/learn/whyvol/eduben/mastersint/)