I have a Solenoid that draws 5 amps at 5 volts how can I go about controlling this with out a relay and also What kind of power supply should I use I tried using 4 AA and they started to heat up really quick.

A 6V lead-acid battery?

Use a cheap 5v 6a or more switching type supply (Ex ebay 290578766909).

To control the solenoid, use an NPN power Darlington rated at more than the 5a, for example the TIP142 (rated at 10a) or the cheaper TIP120 (rated at 5-8a).

Connect the grounds together of your Arduino power and this separate solenoid 5v. Make sure to put a power diode in parallel across the solenoid.

The B of the Earl goes through say a 220 ohm resistor to your Arduino dig out pin. The E goes to your common ground (thicker wire to handle the 5a) The C goes to the neg of the solenoid and cathode of the power diode. The solenoid +V goes to the pos of the solenoid and anode of the power diode.

Draw it out first.