Since I asked these same questions not too long ago, I'll try my best to answer them for you. If you're interested in getting a prehensile tailed skink, you really should get a pair, for both psychological and conservational reasons.
First off I was thinking that I am going to build a cage, is 5 ft. high x 3 1/2 ft. wide x 2 ft. deep large enough? What kind of materials do you suggest to build the cage from?
The tank I will be getting is smaller than that. Your tank is probably big enough to house a trio.
What should I use as hides and how many should I have, at least?
At least two, I'd say. Some people use wicker baskets. The other option would be cork bark tubes/barrels. Check out www.thebeanfarm.com and www.blackjungle.com.
Since they are arboreal do they need a heat matt as well as a lamp or can I do without the matt?
I wouldn't go for the heat mat. Assuming your room temperature is about 70 degrees, you should be fine.
What is the recommended humidity level and temprature?
I believe the recommended humdity is around 70% with the highest temperature being 85 degrees. Be sure the entire cage isn't 85 degrees though, they need to be able to thermoregulate
Since they are nocturnal do they need UV lights?
That's debatable, based on my experience with other animals, I'd say no uvb lights are not required. They definitely need a time and night schedule though. There's not exposed to uvb long enough to produce the vitamin d3 needed to absorb calcium. They should be dosed with a calcium/vitamin d3 supplement on a daily basis. With that said, it wouldn't hurt to have a uvb bulb in there.
How large do these lizards get snout to tail tip?
About 24 inches and more.
Can you give me some links to reputable breeders and fact sites/caresheets online?
herpbreedingresearch.com and a friend of mine buys chondros from http://www.signalherp.com/index.html and recommended inquiring about corucias through them.