I generally play on Epic or Marathon, and am currently still at Noble diff.
One thing that should be factored in here is time it will take to research Bronze Working, as you cannot cut until you have BW. On Epic and Marathon settings, research time is increased, and I am sure that in some cases it may not be possible to have BW researched before 30 turns or more have gone by. Also, at Noble difficulty and higher it can be suicide to avoid building a military unit for any length of time. If your Civ starts with a warrior, you can place it in your first city to avoid losing it to barbs, but you will need to build another before you build your first settler. The problem with this though, is that you do not get to explore much, and this can reduce your options when trying to find a suitable spot for your 2nd city, and increase the number of barbs that harass you.
I quite often play civs that start with a scout though, so exploration is not a problem. The other good thing about starting with a scout at higher difficulty is that they always obtain positive results from huts, you won't have to worry about them turning into barbs. The bad thing is this means that I need to produce a warrior first to defend my capital, or if starting with a warrior, I need to research Hunting first to get scouts quickly enough to start exploring. In the latter case, this delays Bronze Working even more.
My normal progression at the start of the game is this:
Warrior, worker, warrior, settler, worker
Or you can play a custom game and turn off barbs, so that you don't have to worry about your military at the outset.
I tend to avoid cutting, except when improving a tile, this may be a result of the amount of time I spent playing the previous Civ games, and Alpha Centauri, in which clearcutting your natural surroundings seemed to be more detrimental in the long run. Of course, if you only cut early in the game, don't improve the tiles, and leave a few forests around, your forests can grow back over time. This can be effective, and I have used it in situations where I have alot of forest/tundra tiles on the extreme borders of my civ. I avoid planting any cities in the area, unless I need a certain resource there, and cut every other tile before leaving the area alone for a good long time. Once I return a few of the previously cut tiles have grown back, and I can cut them again.