Feathers

Method One: Go outside every morning around dawn.

Not only can you get a few arrows from burnt skeletons, but you can also get some feathers from chickens that happened to die in the night (from wolves, cactus).

Beta 1.7 and earlier: You can also get many feathers from burnt zombies by going out in the early morning.

Method Two: Explore

If you haven't fully explored at least one map, you're not doing enough. You should find many chickens on your travels. Kill ALL the chickens! Sometimes they'll drop more than one feather, meaning you can get a lot of arrows from just a few chickens.

Method Three: Build a chicken farm

This you say you've tried, but I'm adding it for completeness anyway. I have a very low maintenance farm. I place a single torch right outside my front door. That way, at night, that is the only place where passive mobs can spawn (it's the only place with both grass and light). I kill all the cows, chickens, and pigs that spawn right outside my door when I go out every morning at dawn.

Beta 1.9 and later: This should be considerably easier as you can use wheat to breed additional chickens.

Flint

Mine.

You should usually be doing a great deal of this anyway, but whenever you come across a gravel deposit underground, mine it. All of it. You should get a lot of flint from this, and the gravel you get can be used for other things¹ most of which will eventually return more flint.

Sticks are a no-brainer.

These methods (combined with the fact that you only need one of each to make 4 arrows), frequently allow me to have multiple stacks of arrows on hand in case a pesky Ghast should show up.

---

¹Such as descending a large sheer vertical drop. Drop gravel so that it falls into a tower, then you can stand on this tower and mine straight down safely. Bring more gravel than you need, because some will turn to more precious flint.

Hostile Mob Farms will cause you to have more arrows than you need.

I carry around 4 stacks of arrows at all times, and still have a double chest full of arrows sitting in my base, all from one 50 x 50 mob farm.

The key is to do it properly i.e. light up all the caves around you (and preferably build the farm underwater so that even at night mobs won't spawn) and have the trap within range (I think it's like 200 blocks or so) but not so close that mobs won't spawn.

Then you can either pop back every now and then while you're doing your thing, and you'll have a bunch of arrows waiting for you, or just afk for a while and you'll have stacks of arrows in your inventory when you get back.

Enchanting

First mention of the enchantment table in late 2011, and improved for the bow in version 1.1

You can add special ability to your bow with Infinity I to get unlimited arrows for it until it breaks. Sadly, enchanting is random so you don't know what you are going to get. If you want to know more about enchanting, follow that link Minecraft Wiki on Enchanting.

For the bow

http://media-mcw.cursecdn.com/c/c5/EnchantedBow-5.png

Here's a screenshot of a bow boosted with Power V, Punch II, Flame I and Infinity I.

I also heard about an enchantment called Unbreaking : your item will be more resistant (but breakable) depending on the level.

Use enchanting on your bow. It may take a few tries, but eventually you'll get Infinity, which allows you to shoot as many arrows as you want as long as you have one in your inventory, just like creative mode. The bow will break eventually, though. My advice is to use infinity and go outside at night and kill mobs (particularily skeletons), because then you can get arrows, string from spiders to make more bows, and occasionally skeletons drop bows. You also get the drops of other mobs you killed. If you wait till morning then go out and pick up the drops from the mobs that burnt to death, you have the disadvantage of not knowing where they are, and they might despawn or fall into an ocean or something, but you will have the advantage of not having to worry about being killed.

You can name 1 flint, 1 stick and 1 feather in an anvil so you can craft lots of arrows without using any supplies. Just make sure that you have no other unnamed flint, sticks or feathers in your inventory. I tried it and it should work.

1. Find and trap a skeleton.
2. Place two pillars at a perfect diagonal to the skeleton (top block must be transparent)
3. Hide behind two pillars.

The skeleton will shoot at the gap between the pillars and you will collect the arrows