To meet the Army High-Hot standard (4,000 ft, 95 degF) you have to prove that you can hover out-of-ground-effect (OGE).  For Army standards you also must have a 500 ft/min rate of climb capability.  For hand calculations follow this format:

1.  Get Power available @ altitude
  a.  P_avail(alt)=0.90*P_avail(sea-level)*density(alt)/density(sea-level)

Note: The 0.90 term is to account for fuselage downwash, but varies between rotorcraft.  

2.  Determine profile and induced power for both the main rotor and tail rotor.  Since the aircraft is in hover flight, the fuselage parasitic power will be zero.
  a. Vinduced(hover,const alt)=sqrt(TOGW/(2*density(alt)*Area(Main Rotor)))

Note:  2.a only works in hover at constant altitude.

  b. Pinduced=1.15*TOGW*Vinduced

Note: 1.15 is an empirical correction factor.

  c. Cprofile(hover)=Cd0*solidity(MR)/8
  d. Pprofile(hover)=density(alt)*Area(MR)*tipspeed^3*Cprofile(hover)

Warning: Make sure your units are right!!!  If you are working in english units make sure to convert to HP (1 HP=550 ft-lbs/sec).

3. Sum Pinduced and Pprofile, then divide it by the angular velocity of the main rotor, which gives you the torque of the main rotor.
4. To determine the thrust of the tail, divide the main rotor torque by the distance between rotor centers (can be found in Janes AWA).
5. Use the tail thrust instead of TOGW in equations 2.a and 2.b, and wherever you see MR replace with tail rotor (TR), then repeat the equations above to determine the total power required in the tail.
6. Prequired=Prequired(MR)+Prequired(TR)

You may want to divide Prequired by 0.95 to account for transmission losses.

7. R/C(ft/min)=(Prequired(ft-lbs/sec)-Pavail(ft-lbs/sec))/TOGW(lbs)*60sec/1min

If rate of climb (R/C) is 500 ft/min or higher, then your helicopter will meet the Army high-hot conditions.  Good luck, and pay close attention to your units!!!

"It surely will not be 95 deg. F at 4,000 ft. pressure altitude."

Actually, it can be 95 degF at 4,000 ft above sea-level.  Think about Denver, CO.  If you're on the ground, your altitude is around 5,000 ft above sea-level.  The Army High/Hot conditions are talking about altitude above sea-level, not above the ground.  However, these requirements do require you to be able to perform the mission out-of-ground-effect (OGE).  I am a defense contractor, and have performed multiple helicopter analyses at these conditions.  The methodology above is a simplified version of the algorithm I've used in several programs that I have written.  If you want some references, check out these authors Gordon Leishman and Barnes McCormick's.  Wayne Johnson's "Helicopter Theory" book is full of useful information, but may be difficult for someone with little helicopter experience.  I recommend you check out Leishman's book.  It has a lot of good pictures and explanations.  If you're on a tight budget, McCormick's book "Aerodynamics of V/STOL Flight" will probably suffice. I hope this info has been helpful!

Let me restate my comments on the temperature.  The 95 degF is the temperature at sea-level.  In your calculation for air density at altitude, you will need to either determine the temeperature at 4,000 ft or use an equation that accounts for the temperature fall with altitude.  Sorry about that!  Good luck!