You will always have to trade to get Machamp.
The best way to do this really is grab another Gen 3 game that you have and trade and then trade the newly- evolved Machamp back to FireRed. If you don't have any other Gen 3 games (Ruby, Sapphire, Emerald, FireRed and LeafGreen) then arrange a trade with a friend who has a Gen 3 game. If you can't do this, then you can't evolve Machoke. Simple as that.
