How to shrink a table automatically so that it fits onto a page?

You can use \resizebox from the graphicx package. A little example showing the table with and without the use of \resizebox for comparison purposes (I used [!ht] for this example):

\documentclass{article} 
\usepackage{graphicx}
\usepackage{lipsum}% just to generate filler text

\begin{document}  

\lipsum[2]
\begin{table}[!ht]
\centering
\caption{Test caption}
\label{tbl:table1}
\begin{tabular}{|l|l|l|l|}
\hline
Some really reallly long values & 
Some really reallly long values & 
Some really reallly long values & 
Some really reallly long values \\
\hline
\end{tabular}
\end{table}

\lipsum[2]
\begin{table}[!ht]
\centering
\caption{Test caption}
\label{tbl:table2}
\resizebox{\textwidth}{!}{%
\begin{tabular}{|l|l|l|l|}
\hline
Some really reallly long values & 
Some really reallly long values & 
Some really reallly long values & 
Some really reallly long values \\
\hline
\end{tabular}}
\end{table}

\end{document}

If you use two column mode, you can have a wide table using both column by using the a star in \begin{table}:

\begin{table*}

Your table in a two column layout where the table is using both columns:

\documentclass[a4paper,twocolumn]{article}

\usepackage{lipsum,colortbl,graphicx}

\begin{document}

\lipsum[2-10]
\begin{table*}
\centering
\caption{MYCaption}
\label{tbl:table1}

\resizebox{\linewidth}{!}{\begin{tabular}{|l|l|l|l|}
\hline
\rowcolor[gray]{.8}
\multicolumn{4}{|c|}{Team 1}\\
\hline
\textbf{Caption1} & \textbf{Caption 2} & \textbf{Caption3} & \textbf{Caption 4}\\
\hline
Some values & Some values & Some values & Some values\\
\hline
\rowcolor[gray]{.8}
\multicolumn{4}{|c|}{Team 2}\\
\hline
\textbf{Caption1} & \textbf{Caption 2} & \textbf{Caption3} & \textbf{Caption 4}\\
\hline
Some values & Some values & Some values & Some values\\
\hline
\end{tabular}
}
\end{table*}

\lipsum[2-10]

\end{document}