Using one while loop:
In [1]: start = 1
...:
...: while True:
...: if start != 1:
...: do_run = raw_input('Restart? y/n:')
...: if do_run == 'y':
...: pass
...: elif do_run == 'n':
...: break
...: else:
...: print 'Invalid input'
...: continue
...:
...: print 'Doing stuff!!!'
...:
...: if start == 1:
...: start = 0
...:
Doing stuff!!!
Restart? y/n:y
Doing stuff!!!
Restart? y/n:f
Invalid input
Restart? y/n:n
In [2]: