Conventional wisdom isn't very wise. For college grads, the best thing is contacts. Is your dad, uncle or anyone in your network or your family's network or your friend's network a 'big shot' anywhere? If no, the second best thing is work experience. Does your college offer internships or work programs of any kind? If so, join it. Nobody I knew who had internship/work/coop/etc experience in college had trouble finding jobs. Most of them had full-time positions secured before graduation.
> Somehow I don't feel that I'm at a point in my career that I can ditch all my online presence and still get job leads.
During your first job build a contact/network list. You can use that to find the next job. Besides, a significant portion of jobs are word of mouth. For every open position, the manager usually goes around asking if his team knows anyone.
Most people I know don't have linkedin. It's only here where people act like linkedin is a job requirement.