Sudoku generator in Java
Algorithm
Your algorithm is a bit flawed. One might think that it was that easy, but with your current approach one of three things can happen:

The result has exactly one solution (A traditional Sudoku)
The result has many solutions (Not seen as a traditional Sudoku, as there's no way to logically deduce one solution)
The result has no solutions (Yes, although unlikely, this is a possible outcome of your current approach)

A different approach to generating Sudokus is to fill the entire grid first with a valid and completed Sudoku puzzle, and then (pseudocode following):

Remove a number
Check if the current puzzle is solvable using a Sudoku solving algorithm

If it is solvable, continue
If it is not solvable, put the number you just removed back and either try removing another number, or stop.



By using this different approach your result Sudoku is guaranteed to be solvable and have only one solution.
Making it object-oriented
Your main method is doing many many things, I would recommend changing your main method to do only this:
private static final int DEFAULT_SIZE = 9;
public static void main(String[] args) {
    Sudoku sudoku = new Sudoku(DEFAULT_SIZE, DEFAULT_SIZE);
    sudoku.generate(Difficulty.HARD); // Using @Jeroen's lovely enum!
    sudoku.output();
}

With this structure of your main method, you can see that I'm expecting you to create a Sudoku class. You will hopefully see that you will have many benefits by having a specific Sudoku class. By having a Sudoku class, it will be much easier to expand your code, read your code, modify specific parts of your code, and create a world of new amazing Sudoku-ness.
Example of an unsolvable puzzle
For the sake of simplicity, consider a 4x4 puzzle divided into 2x2 boxes:

  12 34
  -----
a|00 03
b|02 04
 |
c|10 00
d|40 00

This puzzle does not break any Sudoku rules in it's current state, however, it is not possible to create a finished Sudoku puzzle from this state!
If you don't believe me, I ask: Which number should be in the top-left corner?

It cannot be a 1, as there is a 1 on position c1.
It can't be a 2 as there's a 2 in the same box on position b2.
It can't be a 3 as there's a 3 on a4.
It also can't be a 4 as there's a 4 on d1.

There is no valid number we can put in the top-left corner, and therefore it is unsolvable!