Always the cheapest fare means that you're limiting what you can do. It seems that every other poster has more or less forgotten this. Splitting up your travel means that you won't get status on anything.

Basically join the program for every airline you fly. Also, it doesn't sound like a credit rating means much to you so you can get every credit card that comes with a bonus and cancel them. That's about the best as you're going to do. People on here spend more than the absolute minimum and consolidate their travel to get rewards. Airlines aren't that interested in rewarding people who only show loyalty to price.