That's what test sets are for! You need training data with examples
xand corresponding labels
y to begin with. Now instead of using everything for training, take a subset of the data, leave it out of training, and check the quality of the generated predictions
y' with respect to the proper labels
x. See http://en.wikipedia.org/wiki/Cross-validation_(statistics) for more details.
OK you're asking for testing "without the correct output", but it's hard for me to imagine how you want to train a machine learning classifier without any training data in the first place. That's why I think the trick of using your training data for that purpose is worth mentioning.
How well your findings on the test set correlate on the true accuracy on your unlabelled data of course is another question, but you can e.g. do multiple rounds of cross-validation (see Wikipedia link for specific patterns like $k$-fold or leave-one-out), or make sure that the distribution of your unknown data is similar to the training data (if it's not, you might have a problem anyway).
To see if your implementation of a specific machine learning algorithm is correct, one way would be to find a paper describing its performance on an openly available dataset, and see if your implementation yields the same results. I've once tried this and got exactly the same performance figures (as in, the same number down to the third digit).