Randomly change the post date (past or future) for your posts to back date/set in future to random dates.
Yes, just leave the category or tag drop downs as they are (set to ALL POSTS)
Yes, you can select to randomly change the date on all posts within a certain category, or all posts with a certain tag
Yes, just change the 'days in past' drop down to however far away in the past you want the maximum possible oldest post
Yes, leave the days in past drop down at 0 and put the days in future for whatever value you want.
Yes, just use both the Days in past and days in future input box.