How to put a full-width table at the top or bottom of the same two-column page as the reference text?

there seems to be no way to put a full-width float at the top of the first page; various mechanisms are used to prevent it, and i haven't found a workaround. (this is most likely also true for the first page of a new chapter in a book or report. maybe frank mittelbach or david carlisle knows a way to do it.)

however, the question states that

At some point, the text ends in the beginning of the first column of a new page.

if it is acceptable to place the float on some page after the first, this is possible, by moving the input for the figure far enough earlier that it is read in (and then delayed) before the page is finished that will be the page preceding the one on which the figure is wanted.

the following example will do this. it's ugly, but it works; it's used in tugboat all the time. (tugboat almost never has the requirement to put such a float at the top of the first page, and if there is such a requirement, we revert to plain tex.) i've added a [t] to request that the float be positioned at the top; it's probably redundant, but it does have the desired effect with some document classes (amsart for one, but apparently not article) if the float ends up as the only thing on the page.

\documentclass{article}
\usepackage{lipsum}

\begin{document}
\twocolumn

\paragraph{}
\lipsum[1-4]

%% this table should appear *before* the paragraph indicated below.
%% it is placed here in the input to force its position at the top of the next page.
\begin{table*}[t]
\centering
\begin{tabular}{|c|c|c|c|}
\hline
Column 1 & Column 2 & Column 3 & Column 4 \\
\hline
Column 1 & Column 2 & Column 3 & Column 4 \\
\hline
\end{tabular}
\end{table*}

\lipsum[5-6]

%% the table coded above should appear at the top of the page on which
%% this paragraph appears.
\paragraph{I want the figure above this text}
\lipsum[1]

\end{document}

EDIT:

the example below will place the figure at the bottom of the page, across both columns, at the cost of an overfull box message. (i'm trying to figure out how to get rid of that, but haven't yet succeeded.)

the approach is to launch a single-column float somewhere in the first column, above where it will start. in the single-column float is embedded a minipage that is the full page width. after the first run, determine by how much the column was shortened, and, somewhere in the second column, issue a negative \enlargethispage command that will leave the bottom part of the page blank, allowing the full-width figure to overflow into the empty area.

\documentclass{article}
\usepackage{lipsum}

\begin{document}

\twocolumn

%% avoid overfull boxes from the lipsum test.
\sloppy

\paragraph{}
\lipsum[1]

%% this table should appear at the bottom of the page.
%% it must be placed in the input somewhere near the top of the
%% first column so that it will actually appear in the first column.
\begin{table}[b]
\begin{minipage}{\textwidth}
\centering
\begin{tabular}{|c|c|c|c|}
\hline
Column 1 & Column 2 & Column 3 & Column 4 \\
\hline

Column 1 & Column 2 & Column 3 & Column 4 \\
\hline
\end{tabular}
\end{minipage}
\end{table}

%% the table coded above should appear at the bottom of the page on which
%% this paragraph appears.
\textbf{I want the figure at the bottom of the page}

\lipsum[1]

\lipsum[2]

%% somewhere in the second column, reduce the page (column) length
%% by the amount needed to clear the figure.
\enlargethispage{-4\baselineskip}

\lipsum[3-6]

\end{document}

yes, it's ugly. don't say you weren't warned.

additional caveat -- the vertical spacing can be fouled up by section headings that have stretch built in. that makes this an iterative process. try to avoid applying this approach until your text is final, and even then, it might be wise to try to "fix" a page break at the top of the page on which the table is to appear.

EDIT 2:

the kludge described here became a tugboat article, "placing a full-width insert at the bottom of two columns", tugboat 35:3 (2014), p.255. (like all tugboat articles in electronic form, this article has a one-year "embargo" during which it is available only to tug members; it will become available to everyone sometime in late fall, 2015.)

one important point mentioned in the article is that the stfloats package, mentioned in Put a table* at the bottom of a page? works only for pages after the first page.