Если коротко, то Нехлюдов — это альтер эго самого Толстого. То есть, брал он его из собственной жизни, писал отчасти с себя. И образ этого персонажа менялся вместе с развитием взглядов писателя (от старшего товарища, удерживающего от дурных поступков до «опрощенца», «евангелиста» и в конце концов — типичного «толстовца»), он в том или ином виде присутствует во многих его произведениях. Так, помимо «Отрочества», «Юности», «Люцерна» и «Утро помещика», где есть собственно Нехлюдов, и главный герой «Казаков» изначально носил эту фамилию, но в процессе написания Толстой заменил ее на фамилию Оленин. А Максим Горький утверждал, причем, считается, небезосновательно, что и в романе «Анна Каренина» Левин — это Нехлюдов. В целом критики прозвали такой тип героя «кающимся дворянином», и у Толстого он окончательно сформировался в романе «Воскресенье». Хотя в первых вариантах он назвал его Юшковым, по фамилии тетки, после изменил на Юшкина, а затем уже и на Нехлюдова. В основе произведения — рассказанный Толстому известным юристом А.Ф. Кони случай о том, как присяжный заседатель во время суда узнал в обвиняемой проститутке некогда соблазненную им девушку, пытался спасти ее и даже жениться. Роман (в набросках — «Коневская повесть») писался в общей сложности 10 лет, за это время писатель пережил духовный кризис, изучал богословие, занимался проповедничеством. И то, что герой в итоге получил «любимую» фамилию, связано еще и с тем, что в жизни Толстого, как признавался он позже в письме своему биографу П.И.Бирюкову, была пара подобных случаев: он совратил крестьянку, о чем намекнул в рассказе «Дьявол», и горничную своей тетки, которую затем выгнали из дома и она погибла...
Что касается происхождения фамилии «Нехлюдов», то, возможно, Толстой использовал ее, опираясь на значение таких слов и соответствующих прозвищ, а затем и фамилий (по Далю и «Ономастикону» С.Б.Веселовского) как «нехлюд, неклюд» - неуклюжий, неустроенный человек. К слову, у славян они еще служили обманными именами-оберегами: так родители называли ребенка в надежде, что он вырастет полной противоположностью этим качествам (ведь «клюдь» — это порядок, приличие, красота). Но это лишь предположение, хотя вот как «неустроенный человек» перекликается с таким выводом из цикла лекций «История русской литературы» все того же Максима Горького: «почти все художественное творчество Толстого сводится к единой теме: найти для князя Нехлюдова место на земле, хорошее место, с которого вся жизнь мира представлялась бы ему гармонией, а он сам себе — красивейшим и величайшим человеком мира».