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.
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 things1 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.
1Such 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.