Is it ever appropriate to cold-email post-docs that have graduate from your program? For context there is a graduate student who has graduate from my program (at my school) working in my subfield (high energy theoretical physics) but he graduated before I joined the program so I never got to introduce myself. 

He's now a post-doc at a highly respected university and is probably extremely busy. 

However, I would really like to reach out to him and ask him for some advice for a beginner in the field, (I'm just starting my second year of the PhD program). Do you think it is appropriate to cold-email him and ask for some advice or the opportunity to speak with him over skype or on the phone or some form of communication?

I feel a little bad because I never introduced myself and I'm really scared of being flat out rejected by him but I also feel that he might have some really good advice for me. 

Mostly, I'm worried about how to write the email and how I might sound (desperate?) to them.
Yes, it's fine. High energy theory is a casual, non-hierarchical, small field of ~2,000 people. If you lived in a town of 2,000 people, you shouldn't be afraid of talking to anyone in it, even the mayor. Here that goes doubly so, as they're only a few years older than you and went to the same school.

As an undergraduate I cold emailed plenty of full professors; some of my friends preferred directly knocking on their doors. The best physicist I know started doing this in high school. I never got any negative feedback, besides occasional admonishment to call them by their first name rather than by their title. In the long run, excessive deference to perceived status will hurt you more than any email ever could.